LeetCode 102 · Trees · concepts: bfs, bfs-pattern

Problem

Return the node values level by level, top to bottom, as a list of lists.

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

Approach — BFS, one level per iteration (optimal)

Standard BFS with a queue, but capture the queue’s size at the start of each outer iteration — that count is exactly the number of nodes on the current level, so you can drain precisely one level at a time.

from collections import deque
 
def levelOrder(root):
    if not root:
        return []
    res, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):        # snapshot: exactly this level's nodes
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        res.append(level)
    return res

Time O(n), space O(n) (up to a full level in the queue).

The len(queue) snapshot

Grabbing len(queue) before the inner loop freezes how many nodes belong to this level; children pushed during the loop belong to the next level and aren’t processed until the next outer pass. This one line is what turns a flat BFS into a level-grouped one.

Key insight

Level-by-level processing → BFS with a per-level size snapshot. This template powers Right Side View (take the last of each level), level averages, zigzag order, and any “do something per level” tree problem — the whole BFS pattern on trees.

↑ Back to NeetCode 150 — Solved