Binary tree level order traversal

Level order traversal is actually a BFS, which is not recursive by nature. It uses Queue instead of Stack to hold the next vertices that should be opened. The reason for it is in this traversal, you want to open the nodes in a FIFO order, instead of a LIFO order, obtained by recursion

as I mentioned, the level order is actually a BFS, and its [BFS] pseudo code [taken from wikipedia] is:

1  procedure BFS(Graph,source):
2      create a queue Q
3      enqueue source onto Q
4      mark source
5      while Q is not empty:
6          dequeue an item from Q into v
7          for each edge e incident on v in Graph:
8              let w be the other end of e
9              if w is not marked:
10                 mark w
11                 enqueue w onto Q

(*) in a tree, marking the vertices is not needed, since you cannot get to the same node in 2 different paths.


void levelorder(Node *n)
{    queue < Node * >q;

     q.push(n);


     while(!q.empty())
     {
             Node *node = q.front();
             cout<<node->value;
             q.pop();
             if(node->left != NULL)
             q.push(node->left);
             if (node->right != NULL)
             q.push(node->right);

     }

}

Tags:

Algorithm