#139

Maximum Width of Binary Tree

medium

treedepth-first-searchbreadth-first-searchbinary-tree

Given the root of a binary tree, return its maximum width.

The width of one level is the distance between its leftmost and rightmost non-null nodes, counting the null slots that would sit between them as if the tree were a complete binary tree. Formally, if you index nodes as in a heap (a node at index i has children 2i and 2i + 1), a level's width is rightmostIndex - leftmostIndex + 1. The answer is the largest level width.

The tree is given as a level-order array where null marks a missing child: [1, 3, 2, 5, 3, null, 9].

Example

Input: root = [1,3,2,5,3,null,9]533129

Output: 4

The bottom level holds 5,3 (under 3) and 9 (under 2's right) at positions 0,1,3 — width 4 including the null gap.

Constraints

The number of nodes in the tree is in the range [1, 3000].
-100 <= Node.val <= 100

Intuition

The width of a level is the distance between its leftmost and rightmost non-null nodes, counting the empty slots that would sit between them in a complete tree. The trick is to give nodes the heap index they'd have in a complete tree: the root is i, its children are 2i and 2i + 1. Then a level's width is just rightmostIndex - leftmostIndex + 1.

function widthOfBinaryTree(root) {
  if (!root) return 0;
  let best = 0;
  let queue = [root];
  while (queue.some((node) => node)) {  // stop when a level is all nulls
    // Trim leading/trailing nulls; the span between real ends is the width.
    let lo = 0;
    let hi = queue.length - 1;
    while (queue[lo] === null) lo++;
    while (queue[hi] === null) hi--;
    best = Math.max(best, hi - lo + 1);
    const next = [];
    for (const node of queue) {        // pad both children, even nulls
      next.push(node ? node.left : null, node ? node.right : null);
    }
    queue = next;
  }
  return best;
}

Brute force — BFS pushing null placeholders for missing children, then measure each padded level.

Padding every null doubles the queue each level — on a sparse, deep tree that's exponential blow-up. Can we avoid materializing the gaps?

The key observation: we never need the empty slots themselves, only the index arithmetic. Carry each real node's heap index alongside it in the queue; a level's width is the last index minus the first plus one. To stop indices from overflowing on deep trees, re-base each level so its first node starts at 0 — only the differences matter.

Tracing [1, 3, 2, 5, 3, null, 9]. Indices (re-based per level): root 1@0; level 1 is 3@0, 2@1; level 2 is 5@0, 3@1 (under 3) and 9@3 (under 2's right). The lane shows the bottom level's occupied indices — the gap at index 2 is the empty slot that widens the span:

bottom level heap indices: 5@0, 3@1, (gap), 9@3 — span 0..3

first↓

·2

leftmost = index 0

5 is the level's first real node, at re-based index 0.

first↓

i↓

·2

3 at index 1

3 (the other child of node 3) sits at index 1.

·2

index 2 empty

Node 2's left child is null — index 2 is a gap, but it still counts toward the span.

first↓

·2

last↓

width = 3 - 0 + 1 = 4

9 (node 2's right child) lands at index 3. Leftmost 0, rightmost 3 → width 4.

Optimization

BFS carrying heap indices

Give the root index 0; a node at index i gives its children indices 2i and 2i + 1 — the positions they'd occupy in a complete tree. Do a level-order traversal carrying each node's index. For each level, the width is lastIndex - firstIndex + 1.

To stop the indices from overflowing on deep trees, subtract the level's first index from every index on that level (re-basing each level to start at 0) — the differences are all that matter.

O(n) time, O(w) space for the queue.

function widthOfBinaryTree(root) {
  if (!root) return 0;
  let best = 0;
  // Queue holds [node, indexWithinLevel]; root starts at 0.
  let queue = [[root, 0]];
  while (queue.length) {
    const first = queue[0][1];
    const last = queue[queue.length - 1][1];
    best = Math.max(best, last - first + 1);
    const next = [];
    for (const [node, index] of queue) {
      // Re-base by 'first' so indices stay small on deep trees.
      const rebased = index - first;
      if (node.left) next.push([node.left, 2 * rebased]);
      if (node.right) next.push([node.right, 2 * rebased + 1]);
    }
    queue = next;
  }
  return best;
}

Complexity analysis

Time complexity: O(n). Here's why:

The BFS carries an index with each node and visits each node once.

So O(n) — the per-level re-basing keeps the index arithmetic O(1) and avoids the brute force's exponential null-padding.

Space complexity: O(w). Here's why:

The queue holds one level of real nodes (with indices) at a time — its width w.

So O(n) worst case, without ever materializing the empty slots between nodes.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
root = [9]9	1	Single node — width 1.
root = [2,4,6,8,10,12,14]8410212614	4	A perfect tree: the bottom level has 4 nodes, no gaps.
root = [5,6,7,8,null,null,9]86579	4	Bottom level: 8 at index 0, 9 at index 3 → width 4 across the gap.
root = [5,6,7,8]8657	2	Level 1 (two nodes) reaches width 2; the bottom node is alone.
root = [5,null,6,null,7]567	1	A right-only spine never exceeds width 1.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor