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 video tutorial 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).
|
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 |
// Binary Level Order Traversal II - Java Code public List<List<Integer>> levelOrderBottomUsingStack(TreeNode root) { //Declare list for output List<List<Integer>> result = new ArrayList<>(); //If root is null, return result if(root == null) return result; //Declare stack and queue Stack<List<Integer>> st = new Stack<>(); Queue<TreeNode> qu = new LinkedList<>(); qu.add(root); //While queue is not empty while(!qu.isEmpty()) { int len = qu.size(); //Store each level values in a list List<Integer> level = new ArrayList<>(); for(int i = 0; i < len; i++) { TreeNode temp = qu.poll(); level.add(temp.val); if(temp.left != null) { qu.add(temp.left); } if(temp.right != null) { qu.add(temp.right); } } //Push in a stack st.push(level); } //Traverse a stack while(!st.isEmpty()) { result.add(st.pop()); } return result; } |
Binary Tree Level Order Traversal II – Java Code
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.
|
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 public List<List<Integer>> levelOrderBottomReverse(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if(root == null) { return result; } Queue<TreeNode> qu = new LinkedList<>(); qu.add(root); while(!qu.isEmpty()) { int len = qu.size(); List<Integer> level = new ArrayList<>(); for(int i = 0; i < len; i++) { TreeNode temp = qu.poll(); level.add(temp.val); if(temp.left != null) { qu.add(temp.left); } if(temp.right != null) { qu.add(temp.right); } } result.add(level); } Collections.reverse(result); return result; } |
Programming questions on binary tree
Check if two binary trees are identical
Binary Tree Reverse Level Order Traversal LeetCode Solution
The other way to solve this problem is to do the level order traversal and put each level result at the 0th index.
|
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 |
//Append each level result at 0th index public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if(root == null) { return result; } Queue<TreeNode> qu = new LinkedList<>(); qu.add(root); while(!qu.isEmpty()) { int len = qu.size(); List<Integer> level = new ArrayList<>(); for(int i = 0; i < len; i++) { TreeNode temp = qu.poll(); level.add(temp.val); if(temp.left != null) { qu.add(temp.left); } if(temp.right != null) { qu.add(temp.right); } } result.add(0, level); } return result; } |
