Binary Tree Level Order Traversal (LeetCode 102)

The problem

You get the root of a binary tree. Return its values level by level, left to right, as a list of lists: one inner list per level, starting from the root.

Input:      3
           / \
          9   20
             /  \
            15   7

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

Level 0 holds 3, level 1 holds 9, 20, level 2 holds 15, 7.

How to think about it

Start with brute force. A DFS can do it: pass the depth down, and append each value to res[depth], creating that list the first time you reach a new depth. Visiting left before right keeps each level in order. It’s O(n), but you’re forcing a depth-first tool onto a breadth-first question.

The key insight: a queue naturally visits nodes level by level. Put the root in. Each time you pop a node, push its children to the back. Because everything on level d was queued before anything on level d + 1, the queue drains one full level before starting the next.

The one extra trick is grouping. The queue alone gives one flat order. To split it into levels, snapshot len(q) at the start of each round: that number is exactly how many nodes belong to the current level. Pop that many into level, and their children (pushed during the round) are the whole next level.

Which pattern is this? Tree BFS. This loop is the template of the lesson: averages, right side view, zigzag, minimum depth and connecting next pointers are all small edits of it. The tell is “level”, “row” or “depth by depth”.

Approach

1. If root is None, return [].
2. Put root in a deque.
3. While the queue is not empty:
   • create an empty level,
   • repeat len(q) times: pop a node, append its value to level, push its left and right children if present,
   • append level to res.
4. Return res.

Solution

from collections import deque

def level_order(root):
    if not root: return []
    res = []; q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):                   # range() fixes the count: this level only
            n = q.popleft(); level.append(n.val)
            if n.left: q.append(n.left)           # next level, queued behind this one
            if n.right: q.append(n.right)
        res.append(level)
    return res
# level_order([3,9,20,null,null,15,7]) -> [[3],[9,20],[15,7]]

range(len(q)) is evaluated once, before the loop starts, so children pushed during the round don’t extend it.

Dry run

On the example tree:

Result: [[3], [9, 20], [15, 7]].

Complexity

• Time: O(n). Each node is pushed and popped once.
• Space: O(w) for the queue, where w is the widest level (up to about n/2 in a complete tree, so O(n) worst case). The output itself is O(n).

Edge cases and pitfalls

• Empty tree: returns [], not [[]].
• Skewed tree (a chain): one node per level, so the result is n single-element lists.
• Pushing None children. Check if n.left before pushing, or you’ll crash on None.val later.
• Using while over the live queue length instead of a fixed count mixes levels together.
• list.pop(0) makes the whole thing O(n²). Use a deque.

Related problems

• Binary Tree Level Order Traversal II (LeetCode 107): the same output, bottom level first.
• Binary Tree Zigzag Level Order Traversal (LeetCode 103): flip direction on alternate levels.
• Average of Levels in Binary Tree (LeetCode 637): reduce each level to its mean.