Binary Tree Level Order Traversal

Return a binary tree's values grouped level by level, left to right. (LC 102)

Where Max Depth teaches tree DFS, this teaches tree BFS — and one specific mechanical idea that carries every "process by level" problem you'll ever see: the level boundary is the queue's length, captured at the top of the level.

The recipe

Say before you type: "A queue holds the current frontier. Before I drain a level, I snapshot how many nodes are in it — everything I enqueue during the drain belongs to the next level."

1. Seed a queue with the root (empty tree → empty answer).
2. While the queue is non-empty: record levelSize = queue.length — the snapshot.
3. Process exactly levelSize nodes: collect each value, enqueue each child.
4. Push the collected level; the queue now holds exactly the next level.

The code

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  let queue: TreeNode[] = [root];
  while (queue.length) {
    const levelSize = queue.length; // SNAPSHOT before mutating
    const level: number[] = [];
    const next: TreeNode[] = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue[i];
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    res.push(level);
    queue = next; // swap arrays — avoids O(n) shift() cost
  }
  return res;
}

Why this shape

BFS visits nodes in distance order, and in a tree "distance from root" is the level. The queue naturally holds a moving frontier — the only problem is that levels blur together as children get enqueued. The snapshot fixes that: at the top of the loop, the queue contains exactly one complete level, so capturing its length tells you precisely how many dequeues belong to this level, no matter how many children you add along the way.

The array-swap detail is a real TypeScript/JavaScript point worth saying out loud: Array.prototype.shift() is O(n) because it reindexes the whole array, so a naive while (queue.length) queue.shift() BFS is quietly O(n²). Swapping in a next array (or walking an index pointer) keeps it honest. Mentioning that unprompted is a strong signal.

Complexity

	Cost	Because
Time	O(n)	Every node is enqueued and dequeued exactly once
Space	O(w)	The queue holds at most one level; the widest level of a full tree is ~n/2

Traps

• Reading queue.length live in the loop condition. If the inner loop's bound is the current length, children enqueued mid-level extend the loop, levels bleed together, and in the worst case the loop never terminates. This exact flipped condition can infinite-loop hard enough to OOM a machine — snapshot first, always.
• Forgetting the empty-tree guard before seeding the queue.
• Using shift() and calling it O(n) per operation when asked — see above.

The pattern this trains

The level-size snapshot is the reusable move: zigzag traversal (LC 103), right side view (LC 199), minimum depth, and every "how many minutes/steps until X" grid problem (Rotting Oranges, LC 994) all drain levels this way. BFS levels = units of distance or time — that equivalence is why BFS answers "shortest" and DFS can't.