# Reverse Level Order Traversal

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.
• 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 q = new LinkedList(); Stack s = new Stack(); 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; } }

view raw
T_ReverseBFS.java
hosted with ❤ by GitHub

Output:

```7 6 5 4 3 2 1
```

### 4 thoughts on “Reverse Level Order Traversal”

1. should’nt the output be like this

4 5 6 7 2 3 1

2. queue insertion order needs to be changed. First insert right child and then left child

• • 