Reverse Level Order Traversal

Reverse Level order traversal of the above tree is “4 5 2 3 1”.

METHOD 1 (Recursive function to print a given level)

// A recursive java program to print reverse level order traversal    // A binary tree node class Node {     int data;     Node left, right;            Node(int item)     {         data = item;         left = right;     } }    class BinaryTree {     Node root;        /* Function to print REVERSE level order traversal a tree*/     void reverseLevelOrder(Node node)     {         int h = height(node);         int i;         for (i = h; i >= 1; i--)         //THE ONLY LINE DIFFERENT FROM NORMAL LEVEL ORDER         {             printGivenLevel(node, i);         }     }        /* Print nodes at a given level */     void printGivenLevel(Node node, int level)     {         if (node == null)             return;         if (level == 1)             System.out.print(node.data + " ");         else if (level > 1)         {             printGivenLevel(node.left, level - 1);             printGivenLevel(node.right, level - 1);         }     }        /* Compute the "height" of a tree -- the number of      nodes along the longest path from the root node      down to the farthest leaf node.*/     int height(Node node)     {         if (node == null)             return 0;         else         {             /* compute the height of each subtree */             int lheight = height(node.left);             int rheight = height(node.right);                /* use the larger one */             if (lheight > rheight)                 return (lheight + 1);             else                 return (rheight + 1);         }     }        // Driver program to test above functions     public static void main(String args[])     {         BinaryTree tree = new BinaryTree();            // Let us create trees shown in above diagram         tree.root = new Node(1);         tree.root.left = new Node(2);         tree.root.right = new Node(3);         tree.root.left.left = new Node(4);         tree.root.left.right = new Node(5);                    System.out.println("Level Order traversal of binary tree is : ");         tree.reverseLevelOrder(tree.root);     } }    // This code has been contributed by Mayank Jaiswal

Output:

Level Order traversal of binary tree is
4 5 2 3 1

METHOD 2 (Using Queue and Stack)

The idea is to use a stack to get the reverse level order. If we do normal level order traversal and instead of printing a node, push the node to a stack and then print contents of stack, we get “5 4 3 2 1” for above example tree, but output should be “4 5 2 3 1”. So to get the correct sequence (left to right at every level), we process children of a node in reverse order, we first push the right subtree to stack, then left subtree.

// A recursive java program to print reverse level order traversal // using stack and queue    import java.util.LinkedList; import java.util.Queue; import java.util.Stack;    /* A binary tree node has data, pointer to left and right children */ class Node {     int data;     Node left, right;        Node(int item)     {         data = item;         left = right;     } }    class BinaryTree {     Node root;        /* Given a binary tree, print its nodes in reverse level order */     void reverseLevelOrder(Node node)     {         Stack<Node> S = new Stack();         Queue<Node> Q = new LinkedList();         Q.add(node);            // Do something like normal level order traversal order.Following         // are the differences with normal level order traversal         // 1) Instead of printing a node, we push the node to stack         // 2) Right subtree is visited before left subtree         while (Q.isEmpty() == false)         {             /* Dequeue node and make it root */             node = Q.peek();             Q.remove();             S.push(node);                /* Enqueue right child */             if (node.right != null)                 // NOTE: RIGHT CHILD IS ENQUEUED BEFORE LEFT                 Q.add(node.right);                               /* Enqueue left child */             if (node.left != null)                 Q.add(node.left);         }            // Now pop all items from stack one by one and print them         while (S.empty() == false)         {             node = S.peek();             System.out.print(node.data + " ");             S.pop();         }     }        // Driver program to test above functions     public static void main(String args[])     {         BinaryTree tree = new BinaryTree();            // Let us create trees shown in above diagram         tree.root = new Node(1);         tree.root.left = new Node(2);         tree.root.right = new Node(3);         tree.root.left.left = new Node(4);         tree.root.left.right = new Node(5);         tree.root.right.left = new Node(6);         tree.root.right.right = new Node(7);            System.out.println("Level Order traversal of binary tree is :");         tree.reverseLevelOrder(tree.root);        } }    // This code has been contributed by Mayank Jaiswal

Output:

Level Order traversal of binary tree is
4 5 6 7 2 3 1