Print binary tree in reverse order – level order traversal (BFS/ java/example)

• Given a binary tree, we would like to print binary tree in reverse order.
• Traverse binary tree using level order traversal or breadth first search algorithm.
• The level order traversal of binary tree is shown in Fig 1:
  • 60 50 90 25 80 75 45
• Binary tree in reverse order using level order traversal is:
  • 45 75 80 25 90 50 60 

Brief algorithm: binary tree in reverse order (non recursive) in java

• Perform level order traversal or breadth first search (BFS).
• Push node value to a stack. (Refer Fig 2: Stack view)
• Print (or Pop) the values from a stack.
• We will get the level order traversal in reverse order.

Algorithm – binary in reverse order (breadth first search) using java

• Initialize the stack. [No element in stack]
• Visit the Level 0 and visit all nodes at Level 0.
  • Visit node 60 and push 60 to a stack [100]
• Visit all nodes of Level 1
  • Visit node 50 & push 50 to a stack [50,60]
  • Visit node 90 & push  90 to a stack [90, 50,60]
• Visit all nodes of Level 2
  • Visit node 25 & push 25 to a stack [25, 90, 50,60]
  • Visit node 80 & push 80 to a stack [80, 25, 90, 50,60]
  • Visit node 75 & push 75 to a stack [75, 80, 25, 90, 50,60]
  • Visit node 45 & push 45 to a stack [45, 75, 80, 25, 90, 50,60]
• Visited all levels of a binary tree.
• Pop all elements from stack & we will get desired output
  • Reverse level order traversal of binary tree:45 75 80 25 90 50 60 

Time complexity of algorithm is O(n).

Program – binary tree in reverse order (BFS) using java

1.) ReverseLevelOrder class: 

• ReverseLevelOrder class print binary tree in reverse order.
• We will traverse the binary tree using level order traversal or depth first search.

 package org.learn.Question;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import org.learn.PrepareTree.Node;

public class ReverseLevelOrder {

 public static void reverseLevelOrder(Node root) {
  if (root == null) {
   System.out.println("Tree is empty");
   return;
  }
  Queue<Node> queue = new LinkedList<Node>();
  queue.offer(root);
  Stack <Node> stack = new Stack<Node>();
  while (!queue.isEmpty()) {
   Node node = queue.poll();
   stack.push(node);
   if (node.left != null) {
    queue.offer(node.left);
   }
   if (node.right != null) {
    queue.offer(node.right);
   }
  }
  while(!stack.isEmpty()) {
   System.out.printf("%d ",stack.pop().data);
  }
 }
}

2.) Node Class: 

Node class representing the nodes of  a binary tree. Node class has following attributes

• Data Node
• left child
• right child

package org.learn.Question;

public class Node {
 public int data;
 public Node left;
 public Node right;

 public Node(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }

 public Node() {
  this.left = null;
  this.right = null;
 }
 
 public static Node createNode(int number) {
  return new Node(number);
 }
}

3.) App Class: 

• We are creating the binary tree in main function.
• We are calling  method of reverseLevelOrder class, to print the binary tree in a reverse order.

package org.learn.Client;

import org.learn.Question.Node;
import org.learn.Question.ReverseLevelOrder;

public class App {
 public static void main(String[] args) {
                // root level 0
  Node A = Node.createNode(60);
  // Level 1
  Node B = Node.createNode(50);
  Node C = Node.createNode(90);
  // Level 2
  Node D = Node.createNode(25);
  Node E = Node.createNode(80);
  Node F = Node.createNode(75);
  Node G = Node.createNode(45);

  // connect Level 0 and 1
  A.left = B;
  A.right = C;
  // connect level 1 and level 2
  B.left = D;
  B.right = E;
  C.left = F;
  C.right = G;
  System.out.println("Reverse Level Order Traversal:");
  ReverseLevelOrder.reverseLevelOrder(A);
 }
}

Output – reverse level order traversal of  binary tree using java

Reverse Level Order Traversal:
45 75 80 25 90 50 60

Code – binary tree in reverse order Level Order Traversal(BFS)