Binary Tree Level Order Traversal II (LeetCode 107)

The problem

You get the root of a binary tree. Return its values level by level, but starting from the deepest level and ending at the root. Inside each level, values still go left to right.

Input:      3
           / \
          9   20
             /  \
            15   7

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

It’s the normal level order [[3], [9, 20], [15, 7]] read from the bottom up.

How to think about it

Start with the tempting wrong idea. “Bottom-up” makes people want to find the leaves first and work upwards. But a tree only has downward pointers, so starting at the bottom means extra parent maps and a lot of fuss.

The key insight: only the order of the levels changes, not their contents. Each inner list is exactly the same as in the top-down version. So compute the ordinary level-order traversal, top to bottom, and reverse the outer list at the end. Reversing is O(number of levels), which is negligible.

Don’t reverse each level’s contents. [9, 20] stays [9, 20]; only the list of levels flips. A common bug is to also reverse inside levels, which gives [[7, 15], [20, 9], [3]].

Which pattern is this? Tree BFS. The tell is “level” in the question. Whenever a variant only changes the order of the levels, reuse the base loop and post-process. (An alternative is res.appendleft(level) on a deque, which builds it in reverse as you go; same complexity.)

Approach

1. Run the standard level-order BFS to get res, a list of levels from top to bottom.
2. Return res[::-1].

Solution

The tested solution reuses level_order from LeetCode 102, included here so the block runs on its own.

from collections import deque

def level_order(root):                            # standard top-down level order (LeetCode 102)
    if not root: return []
    res = []; q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft(); level.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        res.append(level)
    return res

def level_order_bottom(root):
    res = level_order(root)
    return res[::-1]                              # reverse the order of levels only
# level_order_bottom([3,9,20,null,null,15,7]) -> [[15,7],[9,20],[3]]

Dry run

On the example tree:

Complexity

• Time: O(n). The BFS touches each node once; reversing the outer list is O(h) where h is the number of levels.
• Space: O(n). The output holds every value, and the queue holds up to one level (O(w)). res[::-1] makes a new outer list of h references.

Edge cases and pitfalls

• Empty tree: level_order returns [], and reversing it is still [].
• Single node: [[root.val]].
• Reversing inside each level. Only the outer order changes.
• Using res.insert(0, level) in the loop. It works but each insert is O(h), giving O(h²) for a tall tree. Reverse once at the end, or use a deque.
• Thinking you need a bottom-up traversal. You don’t; post-processing is enough.

Related problems

• Binary Tree Level Order Traversal (LeetCode 102): the base traversal this reuses.
• Binary Tree Zigzag Level Order Traversal (LeetCode 103): changes the order within levels instead.
• Average of Levels in Binary Tree (LeetCode 637): another one-line change to the same loop.