Reverse level order traversal

Program to print reverse level order traversal of a binary tree i.e., print data in a binary tree from bottom to top and right to left which is just opposite of normal level order traversal of a binary tree.

Introduction to binary trees

In level order order traversal we traverse each level one by one from top to bottom and left to right. But, in reverse level order traversal we have to traverse from bottom to top and right to left.

Reverse level order traversal

This can be achieved easily by using same approach as we did for normal level order traversal but here we have to use an extra data structure i.e, stack to store the level order traversal and then print it in reverse order.

Here, we are using stack because in stack we can easily reverse the order of data just by pushing and popping the data.

Python

import queue

class Node:
    def __init__(self, data):
        self.left = None
        self.data = data
        self.right = None

def level_order_reverse(root):
    if root:
        q = queue.Queue()
        stack = []
        q.put(root)
        
        while not q.empty():
            node = q.get()
            stack.append(node)
            if node.left:
                q.put(node.left)
            if node.right:
                q.put(node.right)
        
        while stack:
            print(stack.pop().data)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
level_order_reverse(root)

JavaScript

class Node {
  constructor(data) {
    this.left = null;
    this.data = data;
    this.right = null;
  }
}

function levelOrderReverse(root) {
  if (root) {
    const q = [];
    const stack = [];
    q.push(root);

    while (q.length > 0) {
      const node = q.shift();
      stack.push(node);
      if (node.left) {
        q.push(node.left);
      }
      if (node.right) {
        q.push(node.right);
      }
    }

    while (stack.length > 0) {
      console.log(stack.pop().data);
    }
  }
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
levelOrderReverse(root);

Output