Reverse Level Order Traversal | A recursive C # program to print reverse level order traversal using stack and queue ; A binary tree node has data , pointer to left and right children ; Given a binary tree , print its nodes in reverse level order ; 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 ; Dequeue node and make it root ; Enqueue right child ; NOTE : RIGHT CHILD IS ENQUEUED BEFORE LEFT ; Enqueue left child ; Now pop all items from stack one by one and print them ; Driver code ; Let us create trees shown in above diagram
using System . Collections . Generic ; using System ; public class Node { public int data ; public Node left , right ; public Node ( int item ) { data = item ; left = right ; } } public class BinaryTree { Node root ; void reverseLevelOrder ( Node node ) { Stack < Node > S = new Stack < Node > ( ) ; Queue < Node > Q = new Queue < Node > ( ) ; Q . Enqueue ( node ) ; while ( Q . Count > 0 ) { node = Q . Peek ( ) ; Q . Dequeue ( ) ; S . Push ( node ) ; if ( node . right != null ) Q . Enqueue ( node . right ) ; if ( node . left != null ) Q . Enqueue ( node . left ) ; } while ( S . Count > 0 ) { node = S . Peek ( ) ; Console . Write ( node . data + " ▁ " ) ; S . Pop ( ) ; } } public static void Main ( ) { BinaryTree tree = new BinaryTree ( ) ; 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 ) ; Console . WriteLine ( " Level ▁ Order ▁ traversal ▁ of ▁ binary ▁ tree ▁ is ▁ : " ) ; tree . reverseLevelOrder ( tree . root ) ; } }