Skip to main content

Reverse level order traversal of binary tree in java

Java program for Reverse level order traversal of binary tree. Here problem description and explanation.

/*
  Java program for
  Reverse level order traversal of binary tree 
  By using stack and queue
*/
// Binary Tree Node
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
// Create node of (Queue,Stack)
class Node
{
    public TreeNode element;
    public Node next;
    public Node(TreeNode node)
    {
        this.element = node;
        this.next = null;
    }
}
class MyQueue
{
    public Node head;
    public Node tail;
    public int count;
    public MyQueue()
    {
        this.head = null;
        this.tail = null;
        this.count = 0;
    }
    public int size()
    {
        return this.count;
    }
    public boolean isEmpty()
    {
        return this.count == 0;
    }
    // Add new node of queue
    public void enqueue(TreeNode value)
    {
        // Create a new node
        Node node = new Node(value);
        if (this.head == null)
        {
            // Add first element into queue
            this.head = node;
        }
        else
        {
            // Add node at the end using tail 
            this.tail.next = node;
        }
        this.count++;
        this.tail = node;
    }
    // Delete a element into queue
    void dequeue()
    {
        if (this.head == null)
        {
            // Empty Queue
            return;
        }
        // Visit next node 
        this.head = head.next;
        this.count--;
        if (this.head == null)
        {
            // When deleting a last node of linked list
            this.tail = null;
        }
    }
    // Get front node
    public TreeNode peek()
    {
        if (this.head == null)
        {
            return null;
        }
        return this.head.element;
    }
}
// Define a custom stack
class MyStack
{
    public Node top;
    public int size;
    public MyStack()
    {
        // Set node values
        this.top = null;
        this.size = 0;
    }
    public int size()
    {
        return this.size;
    }
    // Add node at the top of stack
    public void push(TreeNode element)
    {
        // Create new node
        Node n = new Node(element);
        n.next = this.top;
        // Make new top
        this.top = n;
        this.size++;
    }
    public boolean isEmpty()
    {
        if (this.size() > 0)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    // Remove top element of stack
    public void pop()
    {
        if (this.size() > 0)
        {
            // Change top element of stack
            this.top = this.top.next;
            this.size--;
        }
    }
    // Return top element of stack
    public TreeNode peek()
    {
        if (this.size() == 0)
        {
            return null;
        }
        return this.top.element;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        // Set initial tree root
        this.root = null;
    }
    public void reverseLevelOrder()
    {
        if (this.root != null)
        {
            MyQueue q = new MyQueue();
            MyStack s = new MyStack();
            // Add first node
            q.enqueue(this.root);
            TreeNode node = this.root;
            while (q.isEmpty() == false && 
                   node != null)
            {
                if (node.right != null)
                {
                    // Add right child node 
                    q.enqueue(node.right);
                }
                if (node.left != null)
                {
                    // Add left child node 
                    q.enqueue(node.left);
                }
                // Add the resultant node
                s.push(node);
                // Remove current node
                q.dequeue();
                // Get new head
                node = q.peek();
            }
            // Display result
            while (s.isEmpty() == false)
            {
                // Get top element
                node = s.peek();
                // Display level node
                System.out.print("   " + node.data);
                // Remove top
                s.pop();
            }
        }
        else
        {
            System.out.println("Empty Tree");
        }
    }
    public static void main(String[] args)
    {
        // Create new tree
        BinaryTree tree = new BinaryTree();
        /*   
            Make A Binary Tree
            -----------------------
                   1
                  / \ 
                 /   \
                2     3
               /     / \
              4     5   6
             /     / \   \
            7     8   9   10
        */
        // Add node
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.right.right = new TreeNode(6);
        tree.root.right.right.right = new TreeNode(10);
        tree.root.right.left = new TreeNode(5);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.left.left = new TreeNode(7);
        tree.root.right.left.left = new TreeNode(8);
        tree.root.right.left.right = new TreeNode(9);
        // Display the reverse level order elements
        tree.reverseLevelOrder();
    }
}

Output

   7   8   9   10   4   5   6   2   3   1




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment