using System.Collections.Generic;
public class BinaryTree {
BinaryTree() { root = null; }
void printInorder(Node node)
Console.Write(node.key + " ");
printInorder(node.right);
void printPreorder(Node node)
Console.Write(node.key + " ");
printPreorder(node.left);
printPreorder(node.right);
void printPostorder(Node node)
printPostorder(node.left);
printPostorder(node.right);
Console.Write(node.key + " ");
void printPostorder() { printPostorder(root); }
void printPreorder() { printPreorder(root); }
void printInorder() { printInorder(root); }
public virtual void printLevelOrder()
for (i = 1; i <= h; i++) {
printCurrentLevel(root, i);
int lheight = height(root.left);
int rheight = height(root.right);
void printCurrentLevel(Node root,
Console.Write(root.key + " ");
printCurrentLevel(root.left, level - 1);
printCurrentLevel(root.right, level - 1);
void printLevelOrderWithQueue()
Queue<Node> queue = new Queue<Node>();
while (queue.Count != 0) {
Node tempNode = queue.Dequeue();
Console.Write(tempNode.key + " ");
if (tempNode.left != null) {
queue.Enqueue(tempNode.left);
if (tempNode.right != null) {
queue.Enqueue(tempNode.right);
void reverseLevelOrder(Node node)
Stack<Node> S = new Stack<Node>();
Queue<Node> Q = new Queue<Node>();
Console.Write(node.key + " ");
public static void Main(String[] args)
BinaryTree tree = new BinaryTree();
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);
"\nInorder traversal of binary tree is ");
"Preorder traversal of binary tree is ");
"\nPostorder traversal of binary tree is ");
Console.WriteLine("Level order traversal "
Console.WriteLine("Level order traversal "
+ "of binary tree with a Queue is");
tree.printLevelOrderWithQueue();
Console.WriteLine("Level Order traversal of binary tree is :");
tree.reverseLevelOrder(tree.root);
For each node, first, the node is visited and then it’s child nodes are put in a FIFO queue. Then again the first node is popped out and then it’s child nodes are put in a FIFO queue and repeat until queue becomes empty.
Follow the below steps to Implement the above idea:
Create an empty queue q and push root in q.
Run While loop until q is not empty.
Initialize temp_node = q.front() and print temp_node->data.
Push temp_node’s children i.e. temp_node -> left then temp_node -> right to q
###Reverse level order with a queue and stack
METHOD 2 (Using Queue and Stack)
The idea is to use a deque(double-ended queue) to get the reverse level order.
A deque allows insertion and deletion at both ends. If we do normal level order traversal and instead of printing a node,
push the node to a stack and then print the contents of the deque, we get “5 4 3 2 1” for the above example tree,
but the output should be “4 5 2 3 1”. So to get the correct sequence (left to right at every level),
we process the children of a node in reverse order, we first push the right subtree to the deque, then process the left subtree.