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

level order traversal binary tree — Fig 1: Traverse binary tree

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.

Fig 2: Stack View

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

reverse binary tree bfs — Fig 3: level order traversal of binary tree

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

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

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

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

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

1.) ReverseLevelOrder class:

2.) Node Class:

3.) App Class:

Output – reverse level order traversal of binary tree using java

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

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

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

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

1.) ReverseLevelOrder class:

2.) Node Class:

3.) App Class:

Output – reverse level order traversal of binary tree using java

You may also like: