Maximum Width of Binary Tree
Max width across levels, counting null gaps between a level's endpoints.
Open on LeetCode ↗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.
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
python
▶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
Edge cases
Sparse deep tree
Indices double per level; normalization keeps them bounded by the level's span.
Single node
Width 1.
06
Complexity
Time
O(n)
Space
O(w)
BFS with positional indices.