4.14.8 — Binary Tree Level Order Traversal

LeetCode 102 · Medium · ★ Blind 75

The problem

Return the node values level by level, top to bottom, left to right within each level.

     3
   /   \
  9    20        →  [[3], [9, 20], [15, 7]]
      /   \
    15     7

The pattern

Any problem that says level, layer, row, or shortest number of steps is breadth-first search. A queue holds the frontier: take a node off the front, put its children on the back.

The one thing that needs care is knowing where one level ends and the next begins, since the queue mixes them.

The fix is one line: capture the queue's length before processing, and loop exactly that many times.

for _ in range(len(queue)):

At the top of each round, the queue holds exactly one complete level. Freezing that count means the children you add during the round belong to the next level and are not touched until the next round.

This line is the template for five problems in this chapter. Get it into muscle memory.

The solution

Python

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

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

        while queue:
            level = []
            for _ in range(len(queue)):        # exactly this level
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)

        return result

TypeScript

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  let queue: TreeNode[] = [root];

  while (queue.length) {
    const level: number[] = [];
    const next: TreeNode[] = [];
    for (const node of queue) {
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    result.push(level);
    queue = next;                              // swap in the next level
  }

  return result;
}

Use a real queue. In Python, collections.deque removes from the front in O(1). A list with pop(0) is O(n) and turns this into a quadratic solution. JavaScript's Array.shift() has the same problem, which is why the TypeScript version builds the next level as a separate array and swaps — a common and clean way to sidestep it entirely.

Push children only if they exist, or the queue fills with nulls that must be filtered later.

Complexity

O(n) time — each node enters and leaves the queue once.

O(w) space, where w is the widest level. For a balanced tree the last level holds about half the nodes, so this is O(n). BFS uses more memory than DFS on a balanced tree (O(n) against O(\log n)), and less on a degenerate one. That trade is why both traversals exist.

The five problems this template solves

Change what you do inside the level loop and you have solved:

problem	change
Level Order	collect all values — this page
Right Side View	keep only the last value of each level — 4.14.9
Average of Levels	sum and divide by the level size
Zigzag Level Order	reverse the list on alternate levels
Minimum Depth	return the level number at the first leaf you meet

Minimum Depth is the one worth pausing on: BFS finds it faster than DFS, because it can stop at the first leaf, while DFS has to explore everything. Whenever "shortest" or "fewest" appears, BFS is usually the right tool — and that becomes the whole argument for BFS in graphs in 4.20.

Doing it with DFS instead

You can produce level order with a depth-first walk, by passing the depth down and appending into the right bucket:

def levelOrder(self, root):
    result = []
    def dfs(node, depth):
        if not node: return
        if depth == len(result):
            result.append([])          # first node seen at this depth
        result[depth].append(node.val)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
    dfs(root, 0)
    return result

It works, it is O(n), and it uses O(h) space instead of O(w). Worth knowing as an answer to "can you do it without a queue", and worth knowing that it cannot stop early the way BFS can.

What the interviewer will push on

"How do you know where a level ends?" The frozen len(queue) at the top of each round.

"Why deque and not a list?" pop(0) is O(n).

"Which uses more memory, BFS or DFS?" BFS is O(w) and DFS is O(h). On a balanced tree BFS is worse; on a degenerate tree DFS is worse.

"Can you do it depth-first?" Yes, by indexing into the result by depth.

"What if the tree is enormous and you only need the first few levels?" BFS stops naturally; DFS would have to be depth-limited.

One thing to volunteer: name the frozen-length line as the level-boundary trick before writing it. Everything else in this problem is routine.

Next: 4.14.9 Binary Tree Right Side View — the same loop with one line changed.