BFS (Breadth first search ) OR Level Order Traversal on tree

Algorithm

• Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we've visited it, process v, and 
• then visit i.e. mark the vertex as visited and process all of v's neighbors. 
• Now that we've visited and processed all of v's neighbors, 
• we need to visit and process all of v's neighbors neighbors

Example
So consider the tree:
      1
   /    \
  2      3
 /   \   /    \
4   5  6   7
The BFS or level order traversal here is :
1 2 3 4 5 6 7

Solution
The BFS solution is not recursive by nature as it uses Queue rather than stack. We will discuss both recursive and non recursive solution.

Non Recursive solution:
BFS is a first in first out search. So, a non-recursive version of BFS can be done using a queue.

Breadth First Search (BFS) searches the graph one level (one edge away from the starting vertex) at a time. In this respect, it is very similar to the level order traversal that we discussed for trees.
Consider the tree:
      1
   /    \
  2      3
 /   \   /    \
4   5  6   7


                                                       Queue

                           -------------------------------------------
                           |  1
                           --------------------------------------------

Visit each element int the queue, enqueue its left and right nodes and dequeue itself. Once the elements are dequeued, I will put them to the left of the queue.
Visit Node 1, enqueue 2 and 3 and dequeue 1

-------------------------------------------
1                             |  2, 3
                              --------------------------------------------

Visit Node 2, enqueue 4 and 5 and dequeue 2

-------------------------------------------
1, 2                         |  3, 4, 5
                             --------------------------------------------

Visit Node 3, enqueue 6 and 7 and dequeue 3

-------------------------------------------
1, 2, 3                     |  4, 5, 6, 7
                            --------------------------------------------

Visit Node 4, dequeue 4 Nothing to enqueue since 4 has no child nodes

-------------------------------------------
1, 2, 3, 4                 |  5, 6, 7
                            --------------------------------------------

Visit Node 5, dequeue 5, Nothing to enqueue since 5 has no child nodes

-------------------------------------------
1, 2, 3, 4, 5             | 6, 7
                          --------------------------------------------

Visit Node 6, dequeue 6, Nothing to enqueue since 6 has no child nodes

-------------------------------------------
1, 2, 3, 4, 5, 6        |  7
                        --------------------------------------------

Visit Node 7, dequeue 7, Nothing to enqueue since 6 has no child nodes

-------------------------------------------
1, 2, 3, 4, 5, 6, 7     |

To perform a BFS, we use a queue. Every time we visit vertex w's neighbors, we dequeue w and enqueue w's neighbors. In this way, we can keep track of which neighbors belong to which vertex. This is the same technique that we saw for the level-order traversal of a tree. The only new trick is that we need to mark the vertices, so we don't visit them more than once.

public void breadthFirstSearch(vertex v)
{
   Queue q = new Queue();

   v.visited = true;
   q.enQueue(v);

   while( !q.isEmpty() )
   {
       Vertex w = (Vertex)q.deQueue();

       // Print the node.
   
       for(each vertex x adjacent to w)
       { 
           if( !x.visited )
           {
              x.visited = true;
              q.enQueue(x);
           }
        }
    }
}

Layer n+1 gets added to the queue when we process layer n. We visit each node only once and each edge at most twice (for edge(v, w), we might encounter it when we're at node v and at node w).

Recursive solution
However recursive solution is not very elegant...(it still uses a queue)

void breadthFirstSearch (Node root){
  Queue q;
  q.push(root);
  bfsRecursiveHelper(q)
}
//Helper function
void bfsRecursiveHelper(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)
  bfsRecursiveHelper(q)
}

Breadth-first traversal traditionally uses a queue, not a stack. The nature of a queue and a stack are pretty much opposite, so trying to use the call stack (which is a stack, hence the name) as the auxiliary storage (a queue) is pretty much doomed to failure, unless you're doing something stupidly ridiculous with the call stack that you shouldn't be.

On the same token, the nature of any non-tail recursion you try to implement is essentially adding a stack to the algorithm. This makes it no longer breadth first search on a binary tree, and thus the run-time and whatnot for traditional BFS no longer completely apply. Of course, you can always trivially turn any loop into a recursive call, but that's not any sort of meaningful recursion.


Thanks.