LeetCode #662 Medium

Maximum Width of Binary Tree

Max width across levels, counting null gaps between a level's endpoints.

treebfsindexing

02

Intuition

Give every node a heap index: root 1, children 2i and 2i+1. Width of a level = last index − first index + 1, regardless of what's missing in between. BFS with (node, index) pairs and compare per level.

How to spot this pattern

Give every node a heap-style index — children of i are 2i and 2i+1 — and a level's width is last - first + 1, gaps included. The normalisation step (subtracting the level's first index) is what prevents those indices from doubling into overflow on deep trees.

03

Approach

1

Heap-style numbering

Indices encode positions in the imaginary complete tree, so gaps count themselves — no null-filling needed.

2

BFS by level

For each level, width = index(last) − index(first) + 1. Track the max.

3

Normalize to prevent overflow

Subtract the level's first index when enqueuing children — keeps numbers small (crucial in fixed-width languages, tidy anywhere).

04

Solution & live demo

▶1from collections import deque
▶2 
▶3class Solution:
▶4    def widthOfBinaryTree(self, root):
▶5        if not root: return 0
▶6        best, q = 0, deque([(root, 0)])
▶7        while q:
▶8            first = q[0][1]
▶9            for _ in range(len(q)):
▶10                node, i = q.popleft()
▶11                i -= first                    # normalize per level
▶12                if node.left: q.append((node.left, 2 * i))
▶13                if node.right: q.append((node.right, 2 * i + 1))
▶14            best = max(best, i + 1)
▶15        return best

05

Common pitfalls

Not normalising indices per level

✗ Wrong

if node.left: q.append((node.left, 2 * i))

✓ Right

i -= first
if node.left: q.append((node.left, 2 * i))

Indices double each level, so a 3,000-deep skewed tree produces astronomically large values — instant overflow in C++/Java and slow big-int arithmetic in Python. Subtracting the level's first index keeps them small while preserving differences.

Counting nodes instead of measuring index span

✗ Wrong

best = max(best, len(q))

✓ Right

best = max(best, i - first + 1)

Width counts the null gaps between the outermost nodes, not just the nodes present. A level with two nodes at indices 0 and 7 has width 8, not 2.

Reading the level's first index after the loop

✗ Wrong

for _ in range(len(q)):
    node, i = q.popleft()
first = i

✓ Right

first = q[0][1]
for _ in range(len(q)):

By the end of the loop the queue holds the next level, so first must be captured before any popping starts. Reading it late normalises against the wrong baseline.

06

Edge cases

Sparse deep tree

Indices double per level; normalization keeps them bounded by the level's span.

Single node

Width 1.

07

Complexity

Time

O(n)

Space

O(w)

BFS with positional indices.