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

Unverified

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

The left child is 2*i and the right child is 2*i+1. Width is the rightmost index minus the leftmost, plus 1.
Raw indices overflow with depth. Subtract the level’s leftmost index before enqueueing children. The difference stays, the values shrink.
One node is 1. A missing left child pushes the right index out. A full level is 2**(h-1) wide.