Reverse Level Order Traversal of Binary Tree

Given a binary tree, print its nodes level by level in reverse order. i.e. all nodes present at last level should be printed first followed by nodes of second-last level 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 4, 5, 6, 7, 2, 3, 1

binary-tree


 

Simple solution would be to print all nodes of level h first, followed by level h-1, .. till level 1 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. 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 reverse 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
s -> empty stack
q.enqueue(root)
while (not q.isEmpty())
    node -> q.dequeue()
    s.push(node)
    if (node.right <> null)
        q.enqueue(node.right)
    if (node.left <> null)
        q.enqueue(node.left)

while (not s.isEmpty())
    node -> s.pop()
    print(node)

 
C++ implementation –
 

Download   Run Complete Code

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 last level. We can also traverse the tree in inorder or postorder fashion.

 
C++ implementation –
 

Download   Run Complete Code

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

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 🙂