Max Width of a Binary Tree
Measure each level using virtual heap indices and track the maximum index span.
Key concepts at a glance — for those who already know the basics.
Problem Statement
Maximum Width of Binary Tree
Input: root = [1, 3, 2, 5, 3, null, 9]
Output: 4
Constraints
- The number of nodes is in range [1, 3000].
- Node values are in range [-100, 100].
01 · The rule
Width at each level is lastVirtualIndex - firstVirtualIndex + 1, not just node count.
Virtual indices keep gap positions that are hidden in sparse trees.
02 · Why virtual indexing
Without index span
You undercount width when missing nodes create large gaps.
With index span
You capture true conceptual width including null positions.
03 · How to think
Run BFS level by level
Store (node, index) in queue where index behaves like heap position.
Read first and last index per level
width = lastIndex - firstIndex + 1 before processing level nodes.
Normalize indices for safety
Subtract first index from all nodes in that level to avoid overflow growth.
Push children using virtual rules
left -> 2*i+1, right -> 2*i+2, then continue to next level.
04 · Diagram
Level 2 has first=1, last=4, so width is 4.
05 · Code
from collections import deque
def widthOfBinaryTree(root):
if not root:
return 0
q = deque([(root, 0)])
ans = 0
while q:
first = q[0][1]
last = q[-1][1]
ans = max(ans, last - first + 1)
for _ in range(len(q)):
node, idx = q.popleft()
idx -= first
if node.left:
q.append((node.left, 2 * idx + 1))
if node.right:
q.append((node.right, 2 * idx + 2))
return ans06 · Complexity
Time
O(n)
Each node is processed exactly once.
Space
O(w)
Queue stores one level at a time, where w is max level width.
07 · Interview uses
LeetCode 662: Exact same max-width formulation with virtual indexing.
Sparse tree layout systems: Index span logic mirrors UI/grid spacing for sparse hierarchies.
Heap-index modeling: Demonstrates confidence in binary heap-style parent/child indexing.
Level-order with metadata: Shows you can augment BFS state for richer interview constraints.
Ready to see it in action?
Step through the visualizer to watch the algorithm state update live.