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)