Level Order Traversal of Binary Tree

Given a binary tree, print its nodes level by level. i.e. all nodes present at level 1 should be printed first followed by nodes of level 2 and so on.. All nodes for any level should be printed from left to right.

For example, the level order traversal for below tree is 1, 2, 3, 4, 5, 6, 7

 
binary-tree


 

We have already discussed preorder, inorder and post-order traversals of the binary tree which are nothing but variations of Depth-first search of a Tree. Trees can also be traversed in level-order, where we visit every node on a level before going to a lower level. This search is referred to as level order traversal or breadth-first search (BFS), as the search tree is broadened as much as possible on each depth before going to the next depth.

 

Simple solution would be to print all nodes of level 1 first, followed by level 2, .. till level h where h is the height of the tree. All nodes present in a level can be printed by modifying pre-order traversal of the tree.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n2).

We can reduce time complexity to O(n) by using extra space. Below is pseudocode for a simple queue based level order traversal which require space proportional to the maximum number of nodes at a given depth. This can be as much as the total number of nodes / 2.


levelorder(root)
q -> empty queue
q.enqueue(root)
while (not q.isEmpty())
    node -> q.dequeue()
    visit(node)
    if (node.left <> null)
        q.enqueue(node.left)
    if (node.right <> null)
        q.enqueue(node.right)

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 


 

We can also solve this problem by using Hashing. The idea is to traverse the tree in preorder fashion and store every node and its level into the multimap using level number as a key. Finally, we print all nodes corresponding to every level starting from first level. We can also traverse the tree in inorder or postorder fashion.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
Exercise:
Modify the solution to print nodes of different levels in separate line.
 

References:
https://en.wikipedia.org/wiki/Tree_traversal
 

Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz