Given a binary tree, write a code to print its reverse level order traversal.
For example:
The reverse or bottom-up level order traversal of this binary tree is 4, 3, 2, 1, 6, 5, 7.
In this example, first we printed last level then second last level and so on. So, we have to start printing the level from bottom-up.
This problem is similar to the level order traversal of a binary tree except in this problem we have to print the level in reverse order.
How we can solve this problem? What’s the time and space complexity of our approach?
Print right view of a binary tree
Reverse Level Order Traversal of a Binary Tree – Java Code
Let’s first discuss the algorithm and then we will write it’s java code. To solve this problem we need two data structure stack and queue.
i) Declare a queue and stack and add root node in a queue.
ii) Run a while loop while the queue is not empty and do the following steps
a) poll a queue and add the node data in a stack.
b) Enqueue (insert in a queue) right and left children of a node if it’s not null.
iii) In the end, traverse a stack and print it’s node data.
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
/* Reverse level order traversal using queue and stack */ public class ReverseLevelOrderTraversal { public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; } } public static void reverseLevelOrderTraversal(TreeNode node) { //Declare a stack which contains integer values Stack<Integer> st = new Stack<>(); //Queue which holds value of TreeNode type Queue<TreeNode> queue = new LinkedList<>(); queue.add(node); while (!queue.isEmpty()) { TreeNode nodeData = queue.poll(); st.add(nodeData.data); //Add right child if (nodeData.right != null) { queue.add(nodeData.right); } //Add left child if (nodeData.left != null) { queue.add(nodeData.left); } } while(!st.isEmpty()) { System.out.print(st.pop()+" "); } } public static TreeNode createBinaryTree() { TreeNode rootNode = new TreeNode(7); rootNode.left = new TreeNode(6); rootNode.right = new TreeNode(5); rootNode.left.left = new TreeNode(4); rootNode.left.right = new TreeNode(3); rootNode.right.left = new TreeNode(2); rootNode.right.right = new TreeNode(1); return rootNode; } public static void main(String[] args) { reverseLevelOrderTraversal(createBinaryTree()); } } |
In this video tutorial, I have explained how to print level order traversal in reverse order using queue and stack data structure.
If you know any other approach which solves this problem efficiently, then let us know through your comment.
