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(n^{2}).

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Function to print reverse level order traversal of given binary tree void reverseLevelOrderTraversal(Node* root) { if (root == nullptr) return; // create an empty queue and enqueue root node list<Node*> queue; queue.push_back(root); // create an stack to reverse level order nodes stack<int> stack; // pointer to store current node Node* curr = nullptr; // run till queue is not empty while (queue.size()) { // process each node in queue and enqueue their children curr = queue.front(); queue.pop_front(); // push current node to stack stack.push(curr->key); // important - process right node before left node if (curr->right) queue.push_back(curr->right); if (curr->left) queue.push_back(curr->left); } // pop all nodes from the stack and print them while (!stack.empty()) { cout << stack.top() << " "; stack.pop(); } } |

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // traverse the tree in pre-order fashion and store nodes into the map // corresponding to their level void preorder(Node *root, int level, auto &map) { // base case: empty tree if (root == nullptr) return; // insert current node and its level into the map map[level].push_back(root->key); // recurse for left and right subtree by increasing level by 1 preorder(root->left, level + 1, map); preorder(root->right, level + 1, map); } // Recursive function to do reverse level order traversal of given tree void levelOrderTraversal(Node *root) { // create an empty map to store nodes between given levels map<int, vector<int>> map; // traverse the tree and insert its nodes into the map // corresponding to the their level preorder(root, 1, map); // iterate through the map using reverse iterator and print all nodes // present in very level for (auto it = map.rbegin(); it != map.rend(); it++) { cout << "Level " << it->first << ": "; for (int i: it->second) cout << i << " "; cout << endl; } } |

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.

**Thanks for reading.**

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 🙂

## Leave a Reply

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 ).

Thanks for bringing this up. We have updated the time complexity.

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