Binary Tree Level Order Traversal II: Bottom-Up BFS

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. That means collecting values level by level from left to right, but starting from the leaf level and ending at the root. This is LeetCode 107: Binary Tree Level Order Traversal II.

For example, given root = [3, 9, 20, null, null, 15, 7], the output is [[15, 7], [9, 20], [3]].

Approach

If you already know how to do standard level order traversal (LeetCode 102), this problem requires only one extra line. The core idea: run normal BFS with a queue, snapshot the queue size at the start of each level, drain exactly that many nodes, and collect each level into a list. Once BFS finishes, reverse the entire result list so the deepest level appears first.

There are two clean ways to produce the bottom-up order:

1. Collect top-down, then reverse. Run standard BFS and build the result list as [[3], [9, 20], [15, 7]]. After the loop, call result.reverse() (or result[::-1]). One extra O(d) operation where d is the number of levels.
2. Insert at the front. Instead of appending each level to the end of the result list, insert it at index 0. This builds the result in bottom-up order on the fly. However, inserting at the front of a Python list is O(d) per insertion, so this approach has slightly worse constant factors.

Both approaches are O(n) overall. The "collect then reverse" version is cleaner because the BFS logic stays completely untouched. That is the version shown below.

The Python solution

from collections import deque

def level_order_bottom(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    result.reverse()
    return result

Here is what each part does:

• queue = deque([root]) initializes BFS with the root node.
• level_size = len(queue) snapshots how many nodes belong to the current level before you start dequeuing them.
• The inner for loop processes exactly one level, collecting values into level and enqueuing children for the next level.
• result.reverse() is the single line that turns standard top-down output into bottom-up output. The deepest level moves to index 0 and the root level moves to the end.

The BFS itself is identical to LeetCode 102. The only addition is one call to reverse() after the loop finishes.

Visual walkthrough

Trace through the tree [3, 9, 20, null, null, 15, 7]. Notice how BFS collects levels in top-down order first. The final reverse step flips the list so leaves come before the root.

The queue always processes nodes left to right within each level, exactly as in standard level order traversal. The bottom-up effect comes entirely from reversing the completed result list. No changes to the BFS loop are needed.

Complexity analysis

The reverse operation adds negligible overhead. It touches d elements (one per level), and d is bounded by n. In practice d is O(log n) for balanced trees.

Building blocks

This problem is built on two core patterns.

BFS level-by-level processing is the main building block. You use a queue and snapshot its size at the start of each level:

from collections import deque

def bfs_levels(root):
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            for child in [node.left, node.right]:
                if child:
                    queue.append(child)

This template appears in LeetCode 102, 103, 107, 199, and many other tree problems. Once you can type it from memory, the level-by-level family of problems becomes a matter of adjusting what you do with each level list.

Result reversal is the second block. After collecting levels top-down, one call to reverse() (or slicing with [::-1]) flips the order. This is the same idea you use anytime you need to reverse a list in place as a post-processing step.

Edge cases

• Empty tree (root is None): return an empty list []. The guard clause at the top handles this.
• Single node (no children): return [[root.val]]. Only one level exists, and reversing a single-element list is a no-op.
• Left-skewed tree (every node has only a left child): each level has one node. The result is [[leaf], ..., [root]], which is the reverse of [[root], ..., [leaf]].
• Right-skewed tree (every node has only a right child): identical behavior to the left-skewed case. One node per level, reversed at the end.

From understanding to recall

You just traced through a bottom-up BFS and saw that the only difference from standard level order traversal is a single reverse() call. It feels obvious now. But in an interview next month, will you remember whether to reverse before or after the BFS loop? Will you recall the level_size = len(queue) snapshot that separates one level from the next?

Reading a solution is not the same as reproducing it under time pressure. Spaced repetition closes that gap. You practice typing the BFS level-by-level template from memory at increasing intervals. First after a day, then three days, then a week. Each repetition reinforces the queue snapshot, the inner loop, and the post-processing reverse until the pattern is automatic.

BFS level-by-level is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Level Order Traversal - The base BFS level-by-level pattern that this problem builds on
• Binary Tree Zigzag Level Order Traversal - Another variation on level order that adds a direction flag instead of a final reverse