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?

Answer 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. :)

Answer 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 ?

Answer 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.