Algorithm

Maximum Width of Binary Tree

Trees Pattern

Maximum Width of Binary Tree

The width of a level is the distance from its leftmost node to its rightmost node, counting the missing positions in between as if they were nodes — as though the level were a full row and only some seats were occupied. Given the root, return the largest width over all levels. Trailing and leading gaps do not count, only the span between the two outermost real nodes.

CONSTRAINTS
  • The number of nodes in the tree is in the range [1, 3000]
  • -100 <= Node.val <= 100
  • Gaps between the outermost nodes of a level count toward its width
  • The answer is guaranteed to fit in a 32-bit signed integer
EXAMPLE 1
Input: root = [1,3,2,5,3,null,9]
Output: 4
The bottom level holds 5, 3 and 9, but 9 sits one seat further right than the missing child of 2. Spanning from 5 to 9 covers four seats, one of which is empty.
EXAMPLE 2
Input: root = [1,3,2,5]
Output: 2
The bottom level contains only 5, so its width is 1. The widest level is the middle one, holding 3 and 2 side by side.
EXAMPLE 3
Input: root = [1,3,2,5,null,null,9,6,null,null,7]
Output: 8
The bottom level holds just 6 and 7, yet they sit at the far outer edges of a row with room for eight, so almost every counted seat is empty. Counting nodes would give 2 and miss the point entirely.
EXAMPLE 4
Input: root = [1]
Output: 1
A single node spans one seat. Width is never zero for a non-empty tree.
Do the gaps really count?
Yes, and that is the whole problem. Counting only real nodes turns this into a trivial exercise and gives wrong answers on sparse levels.
Do gaps outside the outermost nodes count?
No. The measurement runs from the leftmost real node to the rightmost real node, so empty seats beyond either end are ignored.
Can the position numbers get too large?
In principle yes — they double each level, so a 3000-deep tree would need astronomically large numbers. In practice you rebase them per level, which keeps them small. Worth raising in an interview even in languages with big integers.
Is a depth-first solution possible?
Yes: record the first position seen at each depth, then for every node compare its position against that. Breadth-first is more natural because each level's two extremes arrive next to each other.

"Width" here is unusual: not how many nodes a level holds, but how far apart its two outermost nodes are — counting the empty seats between them. So a level with just two nodes can have width 8 if they sit at opposite edges of the row.

That kills the naive idea of grouping each level's nodes and counting them: the missing children were never enqueued, so by the time a level is assembled the holes are gone. We need each node's horizontal seat position, not just which level it's on.

Give every seat a number

Picture each depth as a full, gapless row — depth 0 has 1 seat, depth 1 has 2, depth d has 2^d. Number the seats so a parent's number gives away its children's: root = 0, and a node at seat i has its left child at 2i, its right at 2i + 1.

text
              1(0)
             /    \
          3(0)     2(1)          seat = "which slot if the row were full"
          /  \        \
       5(0)  3(1)      9(3)      <- seat 2 is EMPTY (2 has no left child)

  bottom row seats:  0    1   [2]   3
                     5    3    .    9
  width = last - first + 1 = 3 - 0 + 1 = 4   (the empty seat 2 counted for free)

Why 2i / 2i+1 works: each row is twice as long as the one above, and every parent owns two consecutive seats below it (seat 0 owns 0,1; seat 1 owns 2,3…). Doubling lands on the first owned seat, +1 on the second. So a node's number is exactly the seat it would occupy in a full row — which is the coordinate the problem needs. (Same indexing a binary heap uses in a flat array.)

Now a level's width is pure arithmetic: rightmost seat − leftmost seat + 1. The gaps count themselves — nobody has to know how many children are missing, the subtraction already spanned their empty seats.

python
best, queue = 0, deque([(root, 0)])          # each entry: a node and its seat number
while queue:
    n = len(queue)
    _, first = queue[0]                       # leftmost seat on this level
    last = first
    for _ in range(n):
        node, pos = queue.popleft()
        last = pos                            # the final one seen is the rightmost
        pos -= first                          # rebase, so seats start from 0 again
        if node.left:  queue.append((node.left,  2 * pos))
        if node.right: queue.append((node.right, 2 * pos + 1))
    best = max(best, last - first + 1)
return best

The empty seat 2 was never enqueued and never counted on purpose — 9's seat number (3) already carried the fact that a seat was skipped to its left, so the subtraction picks it up automatically.

Crucial Noteseat numbers double every level, so on a 3000-deep chain a raw number would have ~900 digits and overflow to garbage. Fix: rebase per level — subtract the level's leftmost seat before computing children (pos -= first). Only differences within a level matter, so this keeps every number small while leaving all widths unchanged. And the leftmost node of a level is just the first one dequeued, the rightmost the last — the queue preserves left-to-right order, so no scanning needed.
Cost, and the idea to keep

Each node enqueued and dequeued once, constant work: O(N) time, O(W) queue.

The move worth keeping: when a problem cares about where things would be, not just what's present, track coordinates instead of items. Numbering seats turned "how many holes are in this level?" — a question about absences, which are hard to enumerate — into one subtraction between two real nodes. Coordinates let you measure structure that isn't there.

Interactive Strategy Visualization

Max Width Calculation

Tracing Indices including Nulls

1idx:12idx:23idx:34idx:4idx:5idx:67idx:7

Calculation Step

Start at Root (Index 1). Width: 1

The width is the difference between the indices of the last and first non-null nodes, plus one.
Null nodes count towards index!

Strategy

Focus on the recursive nature of trees: solve for subtrees and combine results at the root.

"Divide and Conquer: Subproblem → Recurrence → Result"

O(N) Time · O(W) Space Position-Indexed BFS
→
Same With Per-Level Rebasing To Avoid Overflow