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 nodeclass 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 |
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 |
Level Order traversal of binary tree is 4 5 6 7 2 3 1
