Binary Tree Level Order Traversal II - Practice Coding Problems

Binary Tree Level Order Traversal II - Problem

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. This means traversing from left to right, level by level from leaf to root.

In other words, collect all nodes at each level, but return the levels in reverse order - starting from the deepest level and ending at the root level.

For example, if a tree has 3 levels, return the nodes in order: Level 3 → Level 2 → Level 1

Input & Output

Example 1 — Basic Tree

$ Input: root = [3,9,20,null,null,15,7]

› Output: [[15,7],[9,20],[3]]

💡 Note: Level order traversal gives [[3],[9,20],[15,7]]. Reversing gives [[15,7],[9,20],[3]] for bottom-up order.

Example 2 — Single Node

$ Input: root = [1]

› Output: [[1]]

💡 Note: Tree has only one level with one node. Result is [[1]].

Example 3 — Empty Tree

$ Input: root = []

› Output: []

💡 Note: Empty tree returns empty result.

Constraints

The number of nodes in the tree is in the range [0, 2000]
-1000 ≤ Node.val ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes at different levels

Level Collection

Group nodes by their depth level

Bottom-Up Output

Return levels in reverse order

Key Takeaway

🎯 Key Insight: Bottom-up traversal = regular level-order + reverse the levels

Asked in

A Amazon 42 M Microsoft 35 F Facebook 28 🍎 Apple 22

The key insight is that bottom-up level order traversal is just regular level-order traversal with the levels reversed. Best approach is BFS with queue to collect levels naturally, then reverse the result. Time: O(n), Space: O(w) where w is maximum tree width.

Common Approaches

Approach	Time	Space	Notes
✓ BFS Level Order + Reverse	O(n)	O(w)	Use BFS to traverse level by level, then reverse the result
DFS with Level Tracking	O(n)	O(h)	Use DFS to collect nodes by level, then reverse the levels

BFS Level Order + Reverse — Algorithm Steps

Step 1: Use queue for BFS traversal
Step 2: Process each level completely
Step 3: Reverse the levels array

Visualization

Tap to expand

Step-by-Step Walkthrough

BFS Queue

Use queue to process nodes level by level

Collect Levels

Store each complete level in array

Reverse Result

Flip the level order for bottom-up

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

static int result[1000][1000];
static int levelSizes[1000];
static int totalLevels = 0;

void solution(struct TreeNode* root) {
    if (!root) {
        printf("[]\n");
        return;
    }
    
    // BFS using array as queue
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    totalLevels = 0;
    memset(levelSizes, 0, sizeof(levelSizes));
    
    queue[rear++] = root;
    
    while (front < rear) {
        int levelSize = rear - front;
        int currentLevel = totalLevels++;
        
        // Process all nodes at current level
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* node = queue[front++];
            result[currentLevel][levelSizes[currentLevel]++] = node->val;
            
            // Add children to queue for next level
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
    }
    
    // Print in reverse order (bottom-up)
    printf("[");
    for (int i = totalLevels - 1; i >= 0; i--) {
        printf("[");
        for (int j = 0; j < levelSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < levelSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i > 0) printf(",");
    }
    printf("]\n");
}

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

int main() {
    // Simple case for demonstration
    struct TreeNode* root = createNode(3);
    root->left = createNode(9);
    root->right = createNode(20);
    root->right->left = createNode(15);
    root->right->right = createNode(7);
    
    solution(root);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once during BFS traversal

✓ Linear Growth

Space Complexity

O(w)

Queue holds at most w nodes where w is maximum width of tree

✓ Linear Space

98.7K Views

Medium Frequency

~15 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS Level Order + Reverse — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler