Tree Breadth-First Search

How It Works

Tree BFS (breadth-first search) visits a binary tree level by level instead of root-to-leaf like DFS. The mechanism is always the same: push the root into a queue, then repeatedly dequeue a node, process it, and enqueue its children. The trick that makes this a distinct pattern rather than plain BFS is tracking level boundaries: you snapshot queue.length at the start of each iteration of the outer loop so you know exactly how many nodes belong to the current level before any of their children get enqueued.

function levelOrder(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length; // freeze the level boundary
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel);
  }

  return result;
}

Everything else in this pattern (right side view, zigzag order, per-level averages, connecting siblings) is a small variation on top of this same loop. You either change what you record per level (first node vs. last node vs. sum) or how you record it (alternate push direction, link node.next before moving on).

When To Use It

Reach for tree BFS when you spot any of these signals:

• The problem literally says "level order", "level by level", or "row by row": that's the strongest signal.
• You need whatever node is visible from one side at each depth, like right side view or left side view: the last (or first) node dequeued per level is your answer.
• You're computing minimum depth: BFS finds the shortest path to the nearest leaf in the first level where one appears, avoiding the need to explore every branch like DFS would.
• You need per-level aggregates: sums, averages, max/min per row, or the width of each level.
• You need to relate nodes at the same depth to each other: connecting siblings with next pointers, or comparing values across a row.

If instead you need to explore full root-to-leaf paths, accumulate state along a path (path sum, valid BST checks), or backtrack, that's tree DFS territory, not this pattern.

Time & Space Complexity

• Time: O(n): every node is enqueued and dequeued exactly once.
• Space: O(n): dominated by the queue, which in the worst case (a completely balanced tree) holds up to n/2 nodes at the widest level. The output array itself is also O(n) since every node's value is recorded once.

Alternative Approaches

• Recursive DFS with a depth parameter: pass the current depth down and push into result[depth], creating a new sub-array the first time you reach a depth. This gets the same level-order groupings without an explicit queue, trading queue space for call-stack space; useful in languages where recursion is cheap, but riskier for very deep/unbalanced trees (stack overflow).
• Two-queue or null-sentinel technique: instead of snapshotting queue.length, push a null marker after each level and treat hitting it as "level complete." This works but is more error-prone than the length-snapshot approach and offers no real benefit; avoid it unless a codebase already uses this style.
• Morris-traversal-style O(1) space tricks exist for some DFS problems but don't meaningfully apply to level-order problems, since you fundamentally need to remember an entire frontier of nodes to know what's next.

Common Mistakes

• Not snapshotting levelSize before the inner loop: if you use queue.length directly as the loop bound while also pushing children inside that same loop, the bound keeps growing and you'll process multiple levels as one.
• Using Array.shift() in a hot loop without realizing the cost: shift() is O(n) on a plain JS array; for large trees, use an index pointer or a proper queue/deque to avoid O(n²) behavior.
• Forgetting to check for null children before enqueueing: pushing null into the queue and then calling .left/.right on it will throw.
• Confusing zigzag order with reversing the whole result at the end: you only reverse alternate levels, not every level, and the traversal itself still proceeds left-to-right; only the order in which you record values into currentLevel flips.
• Building the tree from a LeetCode-style array with null gaps incorrectly: remember that null entries mean "no node here," and children of a null node don't exist in the array at all (this trips people up when re-implementing a tree-from-array helper from scratch).

Pattern Summary

Tree BFS is "plain BFS plus a level boundary." Anytime the question is framed around rows, depths, or "what's visible/aggregated at each level," snapshot the queue size before draining it, and you've got O(n) time with a queue that never holds more than the widest level of the tree.