Reverse Level Order Traversal of Binary Tree Iteratively.

Reverse Level Order Traversal of Binary Tree in Java 

---

In this approach, we will use Stack and Queue for printing reverse level order traversal of Binary Tree. Let us first understand what we want to achieve? what is the input and what will be the expected output?

Algorithm

---

In this approach we need to use Stack because it works as LIFO, data inserted at Last will be read first, so last node added will be read first.

1. Put a Root Node in a Queue.
2. Iterate till the Queue is not Empty.
3. While iterating, take one element from Queue say 50 in our example, put the node in stack and put children's of 50 in queue (Right child first and then Left child if present).
4. Repeat steps till Queue is not empty.

Other popular tree traversals below,

1. pre order traversal of binary tree in java
2. post order traversal of binary tree in java
   
3. in order traversal of binary tree in java
   
4. level order traversal of binary tree using queue in java
5. zigzag traversal of binary tree
   
6. reverse level order traversal of binary tree
   
7. boundary traversal of binary tree
   
8. vertical traversal of binary tree 
   

Java Program for Reverse Level Order Traversal of Binary Tree.

---

package com.javabypatel.tree;

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

public class ReverseLevelOrderTraversalOfBinaryTree {
    /*
    Input:
                     50              Level 0
                  /      \
                 30       70         Level 1
               /   \     /  \
              20   40   60  80       Level 2
             /  \
            10  25                   Level 3

    Output: 10 25 20 40 60 80 30 70 50

            print nodes at level 3  -> 10 25
            print nodes at level 2  -> 20 40 60 80
            print nodes at level 1  -> 30 70
            print nodes at level 0  -> 50
    */
    public static void main(String[] args) {
        new ReverseLevelOrderTraversalOfBinaryTree();
    }

    public ReverseLevelOrderTraversalOfBinaryTree() {
        Node rootNode = null;
        rootNode = addNode(rootNode, 50);
        rootNode = addNode(rootNode, 30);
        rootNode = addNode(rootNode, 70);
        rootNode = addNode(rootNode, 20);
        rootNode = addNode(rootNode, 40);
        rootNode = addNode(rootNode, 10);
        rootNode = addNode(rootNode, 25);
        rootNode = addNode(rootNode, 60);
        rootNode = addNode(rootNode, 80);

        reverseLevelOrderTraversal(rootNode);
    }

    private void reverseLevelOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        Stack<Node> stack = new Stack<Node>();
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);

        while(!queue.isEmpty()) {
            Node node = queue.poll();
            stack.add(node);

            if (node.getRight() != null) {
                queue.add(node.getRight());
            }
            if (node.getLeft() != null) {
                queue.add(node.getLeft());
            }
        }

        while(!stack.empty()) {
            System.out.print(stack.pop().getData() + " ");
        }
    }

    private Node addNode(Node rootNode, int i) {
        if (rootNode == null) {
            return new Node(i);
        } else {
            if (i > rootNode.getData()) {
                Node nodeToAdd = addNode(rootNode.getRight(), i);
                rootNode.setRight(nodeToAdd);

            } else {
                Node nodeToAdd = addNode(rootNode.getLeft(), i);
                rootNode.setLeft(nodeToAdd);
            }
        }
        return rootNode;
    }
}

Node.java

package com.javabypatel.tree;

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

    public Node(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

You may also like to see

---

Top Binary tree interview questions in Java

Serialize and Deserialize a Binary Tree

Find diameter of Binary Tree

Find Kth SMALLEST element in BST(Binary Search Tree)

Check whether Binary Tree is foldable or not.

Check if two nodes are cousins in a Binary Tree.

Get Level/Height of node in binary tree

Print nodes at K distance from Leaf node in Binary tree.

Construct a Binary Tree from In-order and Post-order traversals.

Print Nodes in Top View of Binary Tree.

Zig Zag Traversal of Binary Tree.

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.