Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtree-bfs

Maximum Width of Binary Tree

Problem (restated)

The width of one level is the length between the leftmost and rightmost non-null nodes, counting nulls in between as if the tree were a complete heap. Return the maximum width among all levels.

Intuition

BFS each level while assigning heap indices: left child 2i, right 2i+1. Width = last, first + 1. Normalize indices per level to avoid overflow.

Approaches

BFS with indices

Tested only

Time O(n)Space O(w)

Idea. Queue of (node, index). For each level, record first index, update best with idx, first + 1.

Walkthrough. Root index 0; level with indices 0 and 3 → width 4.

Trade-offs. Index BFS is standard; DFS with depth maps also works.

Solution

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 widthOfBinaryTree(root: TreeNode | null): number {
  if (!root) return 0;
  let best = 0;
  const q: { node: TreeNode; idx: number }[] = [{ node: root, idx: 0 }];
  while (q.length) {
    const size = q.length;
    const base = q[0]!.idx;
    let first = 0, last = 0;
    for (let i = 0; i < size; i++) {
      const { node, idx } = q.shift()!;
      const norm = idx - base;
      if (i === 0) first = norm;
      last = norm;
      if (node.left) q.push({ node: node.left, idx: norm * 2 });
      if (node.right) q.push({ node: node.right, idx: norm * 2 + 1 });
    }
    best = Math.max(best, last - first + 1);
  }
  return best;
}

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 widthOfBinaryTree(root: TreeNode | null): number {
  if (!root) return 0;
  let best = 0;
  const q: { node: TreeNode; idx: number }[] = [{ node: root, idx: 0 }];
  while (q.length) {
    const size = q.length;
    const base = q[0]!.idx;
    let first = 0, last = 0;
    for (let i = 0; i < size; i++) {
      const { node, idx } = q.shift()!;
      const norm = idx - base;
      if (i === 0) first = norm;
      last = norm;
      if (node.left) q.push({ node: node.left, idx: norm * 2 });
      if (node.right) q.push({ node: node.right, idx: norm * 2 + 1 });
    }
    best = Math.max(best, last - first + 1);
  }
  return best;
}

Template connection

Tree BFS with positional indices.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?