Objective: – Given a binary tree, Do the reverse level order traversal. In our earlier post we have seen normal Level Order Traversal. In reverse level order traversal we first need to print the last level followed by second last level up to the root, which is the first level.
Example:
Approach: Use Stack
- Use the Queue and do the level order traversal, read “Level Order Traversal” First if you doesn’t know the technique.
- Instead of printing the Node, keep adding it to Stack.
- At the End print all the nodes from Stack, it will be in reverse order than normal level order traversal.
Code:
| import java.util.LinkedList; | |
| import java.util.Queue; | |
| import java.util.Stack; | |
| public class T_ReverseBFS { | |
| public void reverseBFS(Node root) { | |
| Queue<Node> q = new LinkedList<Node>(); | |
| Stack<Node> s = new Stack<Node>(); | |
| q.add(root);// add the root node to the queue | |
| while (!q.isEmpty()) { | |
| // add the children to the queue | |
| Node n = q.remove(); | |
| if (n.left != null) { | |
| q.add(n.left); | |
| } | |
| if (n.right != null) { | |
| q.add(n.right); | |
| } | |
| // add the extracted node to the Stack | |
| s.add(n); | |
| } | |
| // now print all the Node in Stack | |
| while (s.isEmpty() == false) { | |
| System.out.print(s.pop().data + " "); | |
| } | |
| } | |
| public static void main(String[] args) { | |
| Node root = new Node(1); | |
| root.left = new Node(2); | |
| root.right = new Node(3); | |
| root.left.left = new Node(4); | |
| root.left.right = new Node(5); | |
| root.right.left = new Node(6); | |
| root.right.right = new Node(7); | |
| T_ReverseBFS i = new T_ReverseBFS(); | |
| i.reverseBFS(root); | |
| } | |
| } | |
| class Node { | |
| int data; | |
| Node left; | |
| Node right; | |
| public Node(int data) { | |
| this.data = data; | |
| } | |
| } |
Output:
7 6 5 4 3 2 1
should’nt the output be like this
4 5 6 7 2 3 1
queue insertion order needs to be changed. First insert right child and then left child
Reverse level order means that we will print the last level first and then from there we will go to the root. It does not matter actually whether in a particular level which node you insert first, left or right.
It does matter for the order in which you insert the node into stack. The nodes should always be printed from left to right