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.

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.

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
• JavaScript

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)

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

7
6
5
4
3
2
1

AUTHOR

Abhishek Kumar

Software engineer | Blogger | Keen learner
Python | Django | JavaScript | React | Next.js | Express.js | C
Passionate about learning and experimenting with new things and open to more opportunities and collaborations.