Binary Tree Level Order Traversal II

The output is bottom-up, but the traversal should still be top-down: collect ordinary BFS levels, then reverse the completed groups.

Read the output contract precisely

The problem has three separate ordering requirements:

1. Nodes at the same depth belong in the same inner list.
2. Values within a level stay left to right.
3. The outer list runs from the deepest level back to the root.

That third requirement is the interview trap. It is easy to see “bottom-up” and start designing a reverse traversal. That usually creates unnecessary work. The tree already gives us a natural top-down order through breadth-first search (BFS). We can preserve that reliable traversal and change only how the finished levels are presented.

For this tree:

        3
       / \
      9   20
         /  \
        15   7

Ordinary level order is:

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

The required bottom-up result is:

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

The inner lists are not reversed. Only the order of the levels changes.

For an empty tree, return an empty list:

[]

That distinction gives us the central design decision:

Traverse from the root to the leaves, store each level from left to right, then reverse the outer result.

This is the core of a Binary Tree Level Order Traversal II solution.

Recognize the BFS pattern

The strongest signal is the output shape: values are grouped explicitly by depth. Whenever a problem asks for one group per tree level, BFS should be your first candidate.

A queue naturally models the frontier of a tree:

• Start with the root.
• Remove nodes from the current frontier.
• Add their children to the back of the queue.
• The next frontier contains the next depth.

This is the same per-level collection logic used by ordinary Binary Tree Level Order Traversal. The only difference is the final presentation direction. Zigzag traversal would add a separate direction change within each level; this problem does not. Left-to-right order remains stable throughout.

A depth-first search (DFS) solution is possible. You could recursively track each node’s depth, append values to a list for that depth, and reverse the list of levels afterward. But DFS would make you manage depth-indexed storage even though the problem already gives us a direct level boundary. BFS exposes that boundary more cleanly.

I would not change a working traversal mechanism just because the output is reversed. Separate how data is discovered from how data is returned.

Decompose the algorithm into obligations

The implementation becomes straightforward once each piece of state has a job.

1. Handle the empty root

If root is None, there are no levels:

return []

This also prevents us from placing a null placeholder into the queue.

2. Initialize the queue

Put the root in a queue. The queue stores nodes that have been discovered but not processed.

Use collections.deque, because removing from its left end is designed for queue behavior.

3. Freeze the current level boundary

At the beginning of each outer iteration, capture:

level_size = len(queue)

This number tells us exactly how many nodes belong to the current depth.

That boundary must be captured before processing nodes. While processing the current level, we enqueue children. Those children belong to the next level, even though they increase the queue’s length immediately.

If you repeatedly loop while the queue is nonempty without freezing its original size, you can accidentally process multiple depths as one level.

4. Build the current level

Create an empty list for the current level. Remove exactly level_size nodes:

• Record each node’s value.
• Enqueue its left child if it exists.
• Enqueue its right child if it exists.

The left child must be enqueued before the right child. That preserves left-to-right order in the next frontier.

5. Append the completed level

Once those level_size nodes are processed, append the temporary list to levels.

At this point, levels is still in ordinary top-down order. That is intentional.

6. Reverse the outer list

After BFS finishes, reverse levels:

return levels[::-1]

This changes which level comes first, but it does not alter the values inside any level.

Appending at the end and reversing once is cleaner than inserting every new level at index 0. In Python, front insertion into a list shifts existing elements, adding avoidable work as the number of levels grows. The final reversal keeps the data flow simple: discover, append, reverse.

The queue invariant

The key invariant is more valuable than memorizing the code:

At the start of each outer-loop iteration, the queue contains exactly the unprocessed nodes at one depth, ordered from left to right.

This invariant explains both grouping and ordering.

Assume it is true at the start of an iteration. We capture the queue length, so we process exactly the nodes at that depth. For each node, we enqueue its left child before its right child. Since the current queue was already left-to-right, all children are added in the correct left-to-right order for the next depth.

Therefore, the next iteration begins with another correctly ordered frontier.

By induction, every level is collected exactly once, from the root downward. Each non-null node is removed from the queue once, and its children are considered once, so the loop terminates after all nodes have been processed.

At the end, levels contains:

root level, next level, ..., leaf level

Reversing only the outer list gives:

leaf level, ..., next level, root level

The inner lists remain untouched, so left-to-right ordering is preserved.

That is the whole correctness argument: the queue controls depth boundaries; child enqueue order controls horizontal order; final reversal controls presentation order.

Dry-run the queue and result

Use this tree:

        3
       / \
      9   20
         /  \
        15   7

We will track the queue and the accumulated result.

Before processing depth 0

queue  = [3]
levels = []

The queue size is 1, so this iteration processes only node 3.

• Record 3
• Enqueue 9
• Enqueue 20

After the level:

current_level = [3]
queue         = [9, 20]
levels        = [[3]]

The children were added while processing the root, but they were not processed in the same iteration because level_size was fixed at 1.

Before processing depth 1

queue  = [9, 20]
levels = [[3]]

The queue size is 2, so process exactly 9 and 20.

• Record 9; it has no children.
• Record 20; enqueue 15, then 7.

After the level:

current_level = [9, 20]
queue         = [15, 7]
levels        = [[3], [9, 20]]

Notice the order of the new queue: 15 came from the left child of 20, and 7 came from the right child.

Before processing depth 2

queue  = [15, 7]
levels = [[3], [9, 20]]

The queue size is 2.

• Record 15
• Record 7
• No children are added

After the level:

current_level = [15, 7]
queue         = []
levels        = [[3], [9, 20], [15, 7]]

BFS is complete. Reverse the outer list:

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

The reversal does not turn [15, 7] into [7, 15]. It moves the entire inner list as one unit.

Two quick sanity checks:

root = None
result = []

For a single-node tree:

root = 8
top-down levels = [[8]]
bottom-up result = [[8]]

A one-level tree looks the same in either direction. That is useful, but it does not test the reversal. Always include a tree with at least two depths when checking this algorithm.

Implement the Python solution

Here is an interview-readable Binary Tree Level Order Traversal II Python implementation:

from collections import deque
from typing import Optional


class Solution:
    def levelOrderBottom(
        self, root: Optional["TreeNode"]
    ) -> list[list[int]]:
        if root is None:
            return []

        levels = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)

                if node.left is not None:
                    queue.append(node.left)

                if node.right is not None:
                    queue.append(node.right)

            levels.append(current_level)

        return levels[::-1]

The surrounding interview platform may already define TreeNode, so the quoted annotation is only a compatibility-friendly way to refer to that platform type without redefining it.

Each variable maps directly to an obligation:

• queue holds the next unprocessed frontier.
• level_size freezes the current depth.
• current_level preserves values from left to right.
• levels stores completed levels in discovery order.
• levels[::-1] changes top-down discovery order into bottom-up output order.

The choice of deque matters. popleft() removes the first queued node without shifting every remaining element. A Python list with pop(0) expresses the same conceptual operation, but list front removal shifts the remaining items and can make queue operations unnecessarily expensive.

Complexity

Let n be the number of nodes.

Time: O(n)

Every node is:

• removed from the queue once,
• added to one current-level list once,
• checked for a left child and a right child once.

The final reversal processes the list of levels. There can be at most n nonempty levels, so that work is also O(n) in the worst case.

Together, the traversal and reversal remain:

O(n)

Space: O(n)

The result itself contains every node value, so storing the output takes O(n) space.

The queue holds at most the width of one or nearby tree levels. In a broad tree, that frontier can contain O(n) nodes. The temporary current-level list also contributes to stored output, but the combined auxiliary and result storage remains O(n).

If an interviewer separates output space from working space, you can say:

• Result storage: O(n)
• Queue working space: O(w), where w is the maximum tree width
• Overall space including the returned result: O(n)

That is more precise than claiming the queue always uses O(n) or pretending the output does not count.

Edge cases and common wrong turns

Empty tree

Return [] immediately. Do not return [[]]. There is no empty level to include.

Single node

The result is one inner list containing the root value:

[[root.val]]

No reversal changes it.

Completely skewed tree

For a tree shaped like a linked list, every level has one value:

[[5], [4], [3], [2], [1]]

The queue never becomes wide, but the level boundaries still matter. This case confirms that the algorithm is based on depth rather than on having two children at each node.

Missing children

Do not enqueue null children. A missing child does not represent a value-bearing node or an output position.

Reversing values inside each level

This is wrong:

return [level[::-1] for level in levels[::-1]]

The problem asks for bottom-to-top levels while preserving left-to-right values. Reverse the outer list only.

Traversing right before left

If you enqueue the right child first, the next level may be collected right to left. The final outer reversal cannot repair that inner ordering. Output direction and within-level ordering are separate concerns.

Inserting each level at the front

You can build the answer by inserting each completed level at the beginning, but with a Python list that repeatedly shifts existing elements. It also mixes traversal mechanics with output formatting. Appending normally and reversing once is easier to inspect and defend.

Using DFS by default

DFS is not invalid here. A recursive solution can group values by depth. But it needs an explicit depth parameter and storage for each depth, while BFS gives you the current depth as the queue boundary. Use DFS when the problem’s structure favors path state or recursive relationships; use BFS when the output is naturally organized by frontiers.

The interview recognition rule

When a tree problem asks for values grouped by depth and preserves order within each group, identify a level-boundary BFS.

Before coding, say three things out loud:

1. “The queue contains the next depth’s nodes from left to right.”
2. “I will save the queue length before adding children.”
3. “I will collect levels top-down, then reverse the outer list.”

That explanation exposes the entire solution before syntax gets in the way. The traversal remains ordinary. The queue boundary creates the groups. The final reversal changes only the presentation.

The reusable move is simple: do not redesign discovery to match output direction when a final transformation can handle the difference cleanly.