Reverse Level Order Traversal of a Binary Tree using Recursion

Binary Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given a binary tree, return the reverse level order traversal of its nodes’ values. In reverse level order traversal, we start from the bottom-most level and go up level by level, and within each level, nodes are visited from left to right. The traversal should be done using recursion only.

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 asked to perform a Reverse Level Order Traversal. This means we must visit nodes level by level, starting from the bottom-most level and moving upwards, while still visiting nodes from left to right within each level.

For example, in a normal level order traversal, we go from root to leaves: top to bottom. But in reverse level order traversal, we reverse this and go from bottom to top.

The twist here is that we need to solve it using recursion, which makes it more interesting than the iterative approach with a queue.

Step-by-Step Solution with Example

Step 1: Analyze the Given Tree

Let's consider a sample binary tree:


       1
      /      2   3
    /       4   5   6

The reverse level order traversal of this tree should return: [4, 5, 6, 2, 3, 1]

Step 2: Understand the Goal

We want to collect nodes level-by-level, but instead of printing levels immediately, we will store each level in a list. Once we collect all levels, we will reverse this list to simulate the bottom-to-top traversal.

Step 3: Calculate Tree Height

To traverse level-by-level recursively, we need to know how many levels there are. This can be done by computing the height of the tree first.

Step 4: Traverse and Collect Nodes Level-by-Level

We define a helper function that, given a level number, recursively collects all nodes at that level. We call this function for every level from 1 to the height of the tree and store each result in a list.

Step 5: Reverse the Levels

Once all levels are collected in order from top to bottom, we reverse the entire list of levels. This gives us bottom-to-top ordering.

Step 6: Flatten the Result

Finally, we combine all levels into one single flat list of node values. This will be our final reverse level order traversal.

Edge Cases

Case 1: Tree with Only One Node

If the tree has only the root node (e.g., 1), the output is simply [1]. There's no lower level to reverse, so it's just the root.

Case 2: Empty Tree

If the tree is null or empty, then there are no nodes to visit. The output should be an empty list: []. We must explicitly check for this to avoid null pointer errors during recursion.

Case 3: Skewed Tree (All Left or All Right)

Even if the tree is skewed (e.g., all left children or all right children), the process remains the same — collect level-by-level and reverse at the end.

Finally

This recursive solution builds a clean, structured approach to reverse level order traversal. It helps build an understanding of tree height, level-wise traversal using recursion, and managing order reversal through data structures. It’s beginner-friendly because it separates concerns: one function for height, another for collecting levels, and one final step to reverse and flatten the result.

Remember, recursion is powerful when the problem can be broken into smaller, repeatable tasks — and this problem is a great example of that.

Algorithm Steps❯

  1. Traverse the binary tree recursively level by level starting from the root.
  2. For each level, record the nodes’ values in an auxiliary structure (e.g., an array or list).
  3. After the traversal, reverse the order of the recorded levels.
  4. Concatenate the values from the reversed levels to obtain the reverse level order traversal.

Code

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

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

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

void helper(TreeNode* node, int level, int levels[][100], int* levelSizes, int* maxLevel) {
    if (!node) return;
    if (level > *maxLevel) *maxLevel = level;
    levels[level][levelSizes[level]++] = node->val;
    helper(node->left, level + 1, levels, levelSizes, maxLevel);
    helper(node->right, level + 1, levels, levelSizes, maxLevel);
}

int* reverseLevelOrder(TreeNode* root, int* returnSize) {
    int levels[100][100];
    int levelSizes[100] = {0};
    int maxLevel = -1;
    helper(root, 0, levels, levelSizes, &maxLevel);
    int total = 0;
    for (int i = 0; i <= maxLevel; i++) total += levelSizes[i];
    int* result = malloc(total * sizeof(int));
    int index = 0;
    for (int i = maxLevel; i >= 0; i--) {
        for (int j = 0; j < levelSizes[i]; j++) {
            result[index++] = levels[i][j];
        }
    }
    *returnSize = total;
    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);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    int returnSize;
    int* result = reverseLevelOrder(root, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    free(result);
    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...