#107

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Tree Level Order Traversal II

Return a bottom-up level order traversal of a binary tree, processing nodes left to right while tracking each level accurately in reverse order.

tree breadth first search binary tree

Problem Statement

Given the root of a binary tree, return the bottom-up level order traversal of its node values, traversing each level from left to right. Unlike standard top-down BFS, this requires accumulating each level and then reversing the collected levels so that leaves appear first, and the root appears last. Your solution must handle trees with varying depths and missing children without losing ordering fidelity.

For example, given root = [3,9,20,null,null,15,7], the expected output is [[15,7],[9,20],[3]]. Single-node trees or empty trees must also be correctly processed. Constraints include handling up to 2000 nodes and node values ranging from -1000 to 1000, requiring careful queue management to avoid space inefficiency while preserving the bottom-up level ordering.

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: root = [1]

Output: [[1]]

Example details omitted.

Example 3

Input: root = []

Output: []

Example details omitted.

Constraints

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

Solution Approach

Breadth-First Search with Level Tracking

Start by initializing a queue with the root node and an empty result list. While the queue is not empty, iterate through all nodes in the current level, storing their values in a temporary list. Enqueue each child node for the next level iteration. Once the current level is fully processed, prepend or append to the results in a manner that preserves bottom-up order. This ensures each level is captured completely before moving deeper, avoiding misplacement of node values across levels.

Reverse the Collected Levels

After BFS traversal, the collected levels are in top-down order. Reverse the result list to achieve bottom-up ordering. This can be done efficiently in-place to conserve memory. Care must be taken if using structures like deque or dynamic arrays to ensure the reversal does not disrupt level grouping. This step directly addresses the main requirement of the problem: reporting levels from leaf to root rather than root to leaf, while maintaining left-to-right sequencing within each level.

Edge Case Handling and Optimization

Explicitly check for empty root or single-node trees to avoid unnecessary traversal. For large trees, consider using a deque for O(1) prepend operations to maintain bottom-up order without costly array reversals. Track the number of nodes per level to prevent misalignment between parent and child nodes. These precautions prevent common mistakes such as skipping nodes, duplicating values, or incorrectly ordering levels, which are frequent failure modes in this exact BFS-based traversal problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n), where n is the number of nodes, since each node is visited exactly once during BFS. Space complexity is also O(n), primarily for the queue and the resulting level storage. Both complexities depend on the approach used, but the standard BFS with per-level tracking ensures optimal time and controlled space usage while respecting the bottom-up ordering requirement.

What Interviewers Usually Probe

Do you maintain left-to-right order within each level while collecting nodes?
Can you handle empty trees or single-node trees without extra logic errors?
Will you reverse the levels efficiently without disrupting the BFS ordering?

Common Pitfalls or Variants

Common pitfalls

Prepending each level incorrectly and reversing individual node lists instead of the level list, causing misordered bottom-up traversal.
Failing to account for null children, which can lead to missing nodes or misalignment between parent and child levels.
Using a top-down approach and forgetting to reverse the final result, giving standard level order instead of the required bottom-up output.

Follow-up variants

Binary Tree Level Order Traversal I: Standard top-down level order without reversing, useful for comparing BFS ordering logic.
Zigzag Level Order Traversal: Alternate left-to-right and right-to-left traversal at each level, combining BFS with direction tracking.
Right Side View of Binary Tree: Only collect the rightmost node at each level, which modifies BFS level tracking to selective node capture.

FAQ

What is the main difference between standard level order traversal and Binary Tree Level Order Traversal II?

The key difference is that Level Order Traversal II requires bottom-up ordering. While standard BFS lists levels from root to leaves, this variant reverses the order to start from the leaves.

Can I use DFS instead of BFS to solve this problem?

Yes, DFS can be used by recording node values at each depth and then reversing the collected lists. BFS is often simpler for level tracking, but DFS provides an alternative traversal approach.

How should I handle null children in the tree?

Skip null children when enqueuing nodes for the next level. Properly handling nulls ensures correct alignment of parent and child levels and prevents empty entries in the result.

What are common mistakes when implementing this bottom-up BFS?

Common mistakes include forgetting to reverse the final list, miscounting nodes per level, or accidentally reversing the order of values within each level instead of the overall level order.

How does level tracking affect space usage?

Level tracking requires storing nodes for the current and next levels. Using a queue and temporary lists ensures O(n) space usage, with careful prepending or reversal to avoid extra copies and preserve bottom-up order.

terminal

Solution

Solution 1: BFS

We can use the BFS (Breadth-First Search) method to solve this problem. First, enqueue the root node, then continuously perform the following operations until the queue is empty:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        if root is None:
            return ans
        q = deque([root])
        while q:
            t = []
            for _ in range(len(q)):
                node = q.popleft()
                t.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(t)
        return ans[::-1]

Continue Practicing

#104 maximum depth of binary tree #103 binary tree zigzag level order traversal #111 minimum depth of binary tree