Tree Breadth-First Search Pattern

When to use Tree Breadth-First Search

• The problem asks for level-order traversal, zigzag traversal, or right-side view of a tree.
• You need the minimum depth of a tree (BFS finds the first leaf without exploring the whole tree).
• You need to connect siblings or next-right pointers at each level.
• You need to compute a per-level aggregate (average, max, sum).
• The recursive call stack is too deep for the input size and an iterative approach is required.

Template

function levelOrder(root) {
  if (root === null) return [];
  const result = [];
  const queue = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Common mistakes

• Forgetting to capture `queue.length` before the inner loop, which causes children to leak into the current level as they get appended mid-iteration.
• Using `queue.shift()` in production code on huge inputs — it is O(n) per call on array-backed queues; prefer a real deque or a head-index pointer.
• Pushing null children into the queue and then crashing when dereferencing `.val` on the next iteration.
• Returning the wrong level shape (flat array vs array of arrays) — re-read the expected output format before submitting.
• Using BFS for maximum-depth problems where DFS recursion is simpler; BFS shines for minimum-depth and per-level computation.