Binary tree level order traversal

Question

Three types of tree traversals are inorder, preorder, and post order.

A fourth, less often used, traversal is level-order traversal. In a level-order traveresal, all nodes at depth "d" are processed before any node at depth d + 1. Level-order traversal differs from the other traversals in that it is not done recursively; a queue is used, instead of the implied stack of recursion.

My questions on above text snippet are

1. Why level order traversals are not done recursively?
2. How queue is used in level order traversal? Request clarification with Pseudo code will be helpful.

Thanks!

Answer 1

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.

Answer 2

Instead of a queue, I used a map to solve this. Take a look, if you are interested. As I do a postorder traversal, I maintain the depth at which each node is positioned and use this depth as the key in a map to collect values in the same level

class Solution { public: map<int, vector<int> > levelValues; void recursivePrint(TreeNode *root, int depth){ if(root == NULL) return; if(levelValues.count(root->val) == 0) levelValues.insert(make_pair(depth, vector<int>())); levelValues[depth].push_back(root->val); recursivePrint(root->left, depth+1); recursivePrint(root->right, depth+1); } vector<vector<int> > levelOrder(TreeNode *root) { recursivePrint(root, 1); vector<vector<int> > result; for(map<int,vector<int> >::iterator it = levelValues.begin(); it!= levelValues.end(); ++it){ result.push_back(it->second); } return result; } };

The entire solution can be found here - http://ideone.com/zFMGKU The solution returns a vector of vectors with each inner vector containing the elements in the tree in the correct order.

you can try solving it here - https://oj.leetcode.com/problems/binary-tree-level-order-traversal/

And, as you can see, we can also do this recursively in the same time and space complexity as the queue solution!