Pattern #17

Tree BFS

Recommended

Level-order processing for width, views, and per-level aggregates.

When to use

The answer depends on levels, left-to-right order on a level, or nearest nodes by depth.

Recognition cues

Level order traversal
Right side view / max per level
Zigzag / average of levels

Common pitfalls

Not capturing level size before the loop (queue grows mid-level)
Zigzag forgetting to reverse only the output, not the queue
Using DFS depth when true level order is required

90-second recognition drill

Which pattern fits best?

Level order traversal
Right side view / max per level
Zigzag / average of levels

Tree BFSTwo-Dimensional DPOne-Dimensional DPShortest Path (Weighted)

Interactive

Mental model

A full worked walkthrough of the invariant. Pause, scrub the dots, or use ← →. Aim to narrate each step yourself.

Step 1 of 8

queue = [3] · level 0

Tree BFS is still a real tree. Queue starts with the root only.

How to think about it

Queue the root. For each level, process exactly size = queue.length nodes, enqueueing children. That block is one level. Rightmost (or leftmost) in the block is a side view.

The interactive mental model draws the real tree layout while the queue paints each level: same structure as DFS pages, different traversal order.

Template shapes

Shape	Core move	Notes
Level lists	For i in 0..size-1	Push node.val
Side view	Last (or first) in level	Record once
Zigzag	Alternate reverse	Or deque ends

Complexity baseline

O(n) time and O(w) queue space (w = max width).

From template to problem

Edge case: empty tree.
Queue root; while queue: snapshot size; build level array.
Enqueue children left then right.
Post-process level (reverse, max, average).

Template

Same skeleton in TypeScript, Python, and C#. Adapt the invariant; keep the structure.

Tree BFS · Template

/** Tree BFS template: level-order values. */
export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}
export function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  const q: TreeNode[] = [root];
  while (q.length) {
    const size = q.length;
    const level: number[] = [];
    for (let i = 0; i < size; i++) {
      const n = q.shift()!;
      level.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(level);
  }
  return res;
}

/** Tree BFS template: level-order values. */
export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}
export function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  const q: TreeNode[] = [root];
  while (q.length) {
    const size = q.length;
    const level: number[] = [];
    for (let i = 0; i < size; i++) {
      const n = q.shift()!;
      level.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    res.push(level);
  }
  return res;
}

Path

Start path View in problem browser →

#ProblemTypeDifficultyDone

1#102 Binary Tree Level Order TraversalGuidemedium
2#103 Binary Tree Zigzag Level Order TraversalGuidemedium
3#199 Binary Tree Right Side ViewGuidemedium
4#515 Find Largest Value in Each Tree RowGuidemedium
5#637 Average of Levels in Binary TreeGuideeasy
6#662 Maximum Width of Binary TreeGuidemedium