Recursive breadth-first travel function in Java or C++?

Question

Here is a java code for breadth-first travel:

void breadthFirstNonRecursive(){
    Queue<Node> queue = new java.util.LinkedList<Node>();
    queue.offer(root);
    while(!queue.isEmpty()){
        Node node = queue.poll();
        visit(node);
        if (node.left != null)
            queue.offer(node.left);
        if (node.right != null)
            queue.offer(node.right);
    }
}

Is it possible to write a recursive function to do the same?

At first, I thought this would be easy, so I came out with this:

void breadthFirstRecursive(){
    Queue<Node> q = new LinkedList<Node>();
    breadthFirst(root, q);
}

void breadthFirst(Node node, Queue<Node> q){
    if (node == null) return;
    q.offer(node);
    Node n = q.poll();
    visit(n);
    if (n.left != null)
        breadthFirst(n.left, q);
    if (n.right != null)
        breadthFirst(n.right, q);   
}

Then I found it doesn't work. It is actually does the same thing as this:

void preOrder(Node node) {
    if (node == null) return;
    visit(node);
    preOrder(node.left);
    preOrder(node.right);
}

Has any one thought about this before?

Solution 1

I can't imagine why you'd want to, when you have a perfectly good iterative solution, but here you go ;)

void breadth_first(Node root):
  Queue q;
  q.push(root);
  breadth_first_recursive(q)

void breadth_first_recursive(Queue q):
  if q.empty() return;

  Node n = q.pop()
  print "Node: ", n
  if (n.left) q.push(n.left)
  if (n.right) q.push(n.right)
  breadth_first_recursive(q)

I should add that if you really want to traverse the nodes of the tree recursively, then you could do a DFS with a level parameter, and output nodes only at level, then recurse up. But that's just crazy talk, because you'd revisit nodes wayyyyy too many times... Just accept that BFS is an iterative algorithm. :)

Solution 2

The BFS algorithm is not a recursive algorithm (as opposed to DFS).

One could try writing a recursive function that emulates the algorithm but that would end up quite bizzare. What would be the point in doing this ?

Solution 3

You can use iterative deepening depth-first search, which effectively is a breadth-first algorithm that uses recursion. It's even better than BFS if you have a high branching factor, as it doesn't use much memory.

Solution 4

A Simple BFS and DFS recursion: Just push/offer the root node of tree in stack/queue and call these functions!

public void breadthFirstSearch(Queue queue) {
if (queue.isEmpty()) 
  return;

Node node = (Node) queue.poll();

System.out.println(node + " ");

if (node.right != null) 
  queue.offer(node.right);

if (node.left != null) 
  queue.offer(node.left);

breadthFirstSearch(queue);

}

public void depthFirstSearch(Stack stack) {
if (stack.isEmpty()) 
  return;

Node node = (Node) stack.pop();

System.out.println(node + " ");

if (node.right != null) 
  stack.push(node.right);

if (node.left != null) 
  stack.push(node.left);

depthFirstSearch(stack);

}

Solution 5

Here is an example using arraylist instead of queues, I have predefined the adjacency matrix and the visited array. Also created the edges

    public void BFS(int node, boolean[]visited)
        {
         List<Integer> li=new ArrayList<>();
         for(int j:adj[node])
         {
           if(!visited[j])
             {
                 System.out.println(j+" ");
                 visited[j]=true;
                 li.add(j);
             }
         }
             for(int j:li){
                 BFS(j,visited);
             }
        }

View more solutions

Comments

[gustafc]

The DFS-with-a-level isn't actually that bad idea - it's called iterative deepening depth-first search and is very handy. See my post.

[Stephen]

@gustafc, Thanks, yes I'm aware of iterative deepening, I should've referenced it. I hadn't realized it was only an 11% tax on node visits, that's surprising.

[John G]

This is by far the best answer here.

[prashant]

For Coding interviews. I know of some companies who've asked solving a question using recursive BFS. sigh!