Reverse Level Order Traversal of a Binary Tree using Iteration

Binary Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given a binary tree, return the reverse level order traversal of its nodes' values. Reverse level order means visiting the nodes level by level from bottom to top, and within each level from left to right. Use an iterative approach for the traversal.

Examples❯

Input Tree Reverse Level Order Output Description
[1, 2, 3, 4, 5, null, 6]
[[4, 5, 6], [2, 3], [1]] Standard tree with three levels and both left-right children
[1]
[[1]] Edge case: Tree with a single node (root only)
[] [] Edge case: Empty tree (no nodes at all)
[1, 2, null, 3, null, null, null, 4]
[[4], [3], [2], [1]] Left-skewed tree with increasing depth
[1, null, 2, null, null, null, 3]
[[3], [2], [1]] Right-skewed tree with increasing depth
[7, 4, 9, 2, 5, 8, 10]
[[2, 5, 8, 10], [4, 9], [7]] Complete binary tree with balanced left and right subtrees

Solution❯

Understanding the Problem

We are given a binary tree, and our goal is to perform a reverse level order traversal. That means instead of visiting nodes from top to bottom and left to right (like in standard level order), we visit nodes from the bottom level up, and within each level, from left to right.

This problem tests your understanding of tree traversal techniques, especially level order traversal using a queue, and how to reverse the result using a stack. We'll go through this step-by-step using an example to help build your intuition.

Step-by-Step Solution with Example

Step 1: Understand the Tree Structure

Let's consider the binary tree represented as: [1, 2, 3, 4, 5, null, 6]. Visually, it looks like this:


        1
       /       2   3
     /         4   5    6

Step 2: Use a Queue for Level Order Traversal

We start from the root (node 1) and traverse level by level using a queue. We enqueue the right child before the left child so that when we later reverse the result using a stack, the left-to-right order of nodes is preserved in each level.

Step 3: Push Visited Nodes into a Stack

As we process nodes from the queue, we push each visited node into a stack. This stack helps us reverse the traversal order — since the last nodes processed will come first when popping from the stack.

Step 4: Pop from the Stack for Final Result

Once all nodes have been processed in the queue, we pop elements one by one from the stack to build our final result: the reverse level order traversal.

Step 5: Apply the Steps to the Example

Queue processing order: 1 → 3 → 2 → 6 → 5 → 4 (right before left)

Stack content after traversal: [1, 3, 2, 6, 5, 4]

Final result after popping from stack: [4, 5, 6, 2, 3, 1]

Edge Cases

Case 1: Empty Tree

If the tree is empty (i.e., root is null), then there are no nodes to traverse. We simply return an empty list.

Case 2: Single Node Tree

If the tree has only the root node, the reverse level order traversal is just the value of that single node.

Case 3: Left-Skewed or Right-Skewed Tree

Even in skewed trees (where nodes exist only on one side), the algorithm works correctly — the queue processes each level one by one, and the stack ensures reverse order is achieved.

Finally

This iterative approach to reverse level order traversal is efficient and beginner-friendly. Using a queue to simulate level order traversal and a stack to reverse the result gives us full control over the output structure.

It's important to understand why we enqueue right before left — it ensures the final popped order respects left-to-right orientation per level. Mastering this pattern will help you in many other tree-related problems involving bottom-up traversal.

Algorithm Steps❯

  1. If the binary tree is empty, return an empty result.
  2. Initialize an empty queue and push the root node onto it.
  3. Initialize an empty stack.
  4. While the queue is not empty, dequeue a node from the front, push it onto the stack, then enqueue its right child (if it exists) followed by its left child (if it exists).
  5. Once the queue is empty, pop all nodes from the stack and record their values. This produces the reverse level order traversal.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int* reverseLevelOrder(TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    TreeNode** queue = malloc(100 * sizeof(TreeNode*));
    TreeNode** stack = malloc(100 * sizeof(TreeNode*));
    int front = 0, rear = 0, top = -1;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode* node = queue[front++];
        stack[++top] = node;
        if (node->right) queue[rear++] = node->right;
        if (node->left) queue[rear++] = node->left;
    }
    int* result = malloc(100 * sizeof(int));
    int index = 0;
    while (top >= 0) {
        result[index++] = stack[top--]->val;
    }
    *returnSize = index;
    free(queue);
    free(stack);
    return result;
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    int returnSize;
    int* res = reverseLevelOrder(root, &returnSize);
    printf("Reverse Level Order Traversal: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");
    free(res);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...