Reverse Level Order Traversal - Binary Tree

We can do a reverse level order traversal of a binary tree (i.e. visit last level left-to-right, then visit second to last level left-to-right, and so on all the way up to the first level) using a queue and a stack. Here's a possible implementation:

void reverseLevelOrder(Node *root) {
  if (root == nullptr) return;

  queue<Node *> qu;
  stack<Node *> st;
  qu.push(root);
  while (!qu.empty()) {
    Node *curr = qu.front();
    qu.pop();
    st.push(curr);
    if (curr->right != nullptr) {
      qu.push(curr->right);
    }
    if (curr->left != nullptr) {
      qu.push(curr->left);
    }
  }

  while (!st.empty()) {
    cout << st.top()->value << '\n';
    st.pop();
  }
}

Time complexity

The time complexity is O(n) (where n is the number of nodes in the tree) because of the work we do in the two while loops. See the video for more detail.

Space complexity

The space complexity is O(n) (where n is the number of nodes in the tree) because of the space taken by the queue and the stack. See the video for more detail.

Video with explanation