Binary Tree Level Order Traversal II. Given a binary tree, return the bottom-up level order traversal of its node’s values. (ie, from left to right, level by level from leaf to root).
OR
Given a binary tree, return the reverse level order traversal of its nodes’ values. (i.e, from left to right and from the last level to starting level).
For Example –
In this example, we have printed the reverse level order traversal of a binary tree.
As you can see in this image, we have first printed the last level from left to right then we move up, and so on. We have already discussed the level order traversal in my previous tutorial. So, let’s think about how we can print the reverse level order traversal of a binary tree.
In this tutorial, I am going to discuss three approaches to solve this problem. Also, I have added a videotutorial link at the end of this post.
Binary Tree Reverse Level Order Traversal
Binary Tree Reverse Level Order Traversal using Stacks and Queues – Java Code
In this example, I am going to discuss how we can do the reverse level traversal using Queue and Stack data structure.
The idea here is to do the level order traversal of a binary tree and put the values in a stack. Once traversal is complete, traverse the stack and put the values in a final result list.
The time complexity of this approach is O(n) and its space complexity is also O(n).
Traverse the binary tree level by level. Once the traversal is complete reverse the result list. In this way, we get the reverse level order traversal of a binary tree.
Java
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
//Reverse the result list using collections reverse
