Example 1
ready- Input
root = [ 1, 3, 2, 5, 3, null, 9 ]- Expected
4- Why
- the third level spans four complete-tree positions
Maximum Width
35 min · widthOfBinaryTree()mediumOpen in LeetCode #662 ↗
Two employees can sit at opposite ends of an org-chart row even when several empty positions lie between them. Those gaps still make the row wide.
Given the root of a binary tree, return the largest width among all depths. A level's width is the distance from its leftmost present node to its rightmost present node, including the missing positions between them.
Use complete-tree positions to measure that distance: place the root at position 1;
a node at position i would place its left child at 2 * i and its right child at
2 * i + 1. For each level, compute rightmost - leftmost + 1.
Ground rules:
- Missing positions inside the two extremes count toward the width.
- Missing positions outside those extremes don't count.
- Return
0for an empty tree.
Constraints
0 <= node count <= 3_000- The root is at depth
0, and no node has depth greater than30. -1_000 <= node.val <= 1_000- Every level width fits in a signed 32-bit integer.
Hints
Carry more than the node
Queue each node together with the position it would occupy in a complete tree. The first and last positions in one level determine that level's width.
Freeze one level
Save the queue length before processing. Read exactly that many node-position pairs, then compare the level's span with the best span seen so far.
Keep positions small
Before creating child positions, subtract the first position in the current level from every position. A shared shift doesn't change the width.
Follow-up
If the depth cap disappeared, why would normalizing positions at every level protect languages with fixed-width integers?
Visible cases
Examples
Example 2
ready- Input
root = [ 1, 3, 2, 5, null, null, 9, 6, null, null, 7 ]- Expected
8- Why
- the deepest nodes sit eight positions apart when the gaps count
Example 3
ready- Input
root = [ 1 ]- Expected
1- Why
- one node occupies one position
Interview signal
Asked at
AmazonGoogleBloomberg
Direct position indices — measure the complete-tree slots
Pair each queued node with its complete-tree position. Because the queue keeps a level in left-to-right order, the first and last positions give its width.
from collections import deque
def width_of_binary_tree(root: TreeNode | None) -> int:
if root is None:
return 0
best = 0
queue = deque([(root, 1)])
while queue:
level_size = len(queue)
leftmost = queue[0][1]
rightmost = leftmost
for _ in range(level_size):
node, position = queue.popleft()
rightmost = position
if node.left is not None:
queue.append((node.left, 2 * position))
if node.right is not None:
queue.append((node.right, 2 * position + 1))
best = max(best, rightmost - leftmost + 1)
return bestThis works under the depth cap, but raw positions double on every step downward. A much deeper sparse tree can overflow a fixed-width integer — a number stored with a set count of bits — even when its answer is small.
Time O(n) — every node is handled once. Space O(w) — the queue holds at most
the w nodes present on the widest stored level.
Normalized position indices — preserve spans, drop the growth
The pattern is breadth-first level-order traversal (BFS): visit one depth at a time
with a queue, a first-in, first-out collection. The level-size trick means saving
len(queue) before the inner loop. At each level, subtract its first position before
creating child positions.
from collections import deque
def width_of_binary_tree(root: TreeNode | None) -> int:
if root is None:
return 0
best = 0
queue = deque([(root, 0)])
while queue:
level_size = len(queue)
offset = queue[0][1]
first = 0
last = 0
for index in range(level_size):
node, raw_position = queue.popleft()
position = raw_position - offset
if index == 0:
first = position
last = position
if node.left is not None:
queue.append((node.left, 2 * position))
if node.right is not None:
queue.append((node.right, 2 * position + 1))
best = max(best, last - first + 1)
return bestSubtracting the same offset from every position preserves last - first. Building the
next level from those shifted positions keeps the numbers tied to that level's span
instead of the tree's absolute depth.
Time O(n) — each node enters and leaves the queue once. Space O(w) — only one level's pending nodes and positions are stored.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
4
Run: visible + custom · Submit: full suite