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

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 thin开发者_运维技巧g 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?

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

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 ?

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.

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);

}

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);
             }
        }

This is not going to be satisfying to everyone -- I am sure. With all respect to everyone. To the people who ask what is the point? The point is that we believe that every iterative algorithm has also a (easy?) recursive solution. Here is a solution by "sisis" from stackoverflow.

BFS(Q)

{

  if (|Q| > 0) 

     v < - Dequeue(Q)

     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

It has certain amount of funninest in it, but it not clear that it violates any recursive rules. If it does not violate any recursive rules, then it should be accepted. IMHO.