# 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

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 –

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 –

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

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

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
Michael Keating

For the ‘simple solution’, it seems a post-order traversal would work. Also, it seems, if I’m not mistaken, that the time complexity would be O(N logN), since it’s N (the traversal) times Log N (the height of the tree ).

Guest

We can simply solve this using one queue and string manipulation.

To improve the efficiency, you can use StringBuilder for concatenation.

Time Complexity : O(n) , n : Number of nodes in Binary Tree.
Space Complexity : O(2^h), h : Height of the tree