Maximum Width of Binary Tree
Maximum Width of Binary Tree is LeetCode 662 (Medium). Given the root of a binary tree, return the largest width among all its levels.
The width of a level is measured from its leftmost to its rightmost non-null node, counting the empty positions in between as if that level were complete. A level with nodes only at its two ends is as wide as a full one.
The answer is guaranteed to fit in a 32-bit signed integer.
- The number of nodes in the tree is in the range [1, 3000].
- -100 <= Node.val <= 100
Intuition
Counting the nodes on each level is not enough, because the gaps between the end nodes count too. The trick is to give every node a position number, as in an array-based heap: a node at position p has its children at 2p and 2p + 1.
Missing nodes still use up their numbers, so the span between the leftmost and rightmost positions on a level is the width of binary tree at that level, nulls included. A level-by-level walk sees each level's two ends together, and the maximum width of binary tree is the largest such span. Positions double at every level, which is why the numbering must be kept small.
A question about each level of a tree points to BFS. When the answer depends on where nodes would sit in a complete tree (gaps, columns, alignment), index the nodes like a heap: 2p and 2p + 1.
Approach
Before reading on, try it on [1, 3, 2, 5, null, null, 9]: level 2 has only two nodes but width 4. How can you know how many empty slots lie between them without drawing them?
Number the root and start a level list
Store (node, position) pairs, starting with [(root, 0)]. Carrying the position next to each node is what lets missing nodes count: the numbers skip over the gaps even though nothing is stored for them.
Measure each level
The pairs on a level are in left-to-right order, so width = last_pos - first_pos + 1; update best with it. Only the two end positions matter, which is why the null nodes in between never need to be stored or visited.
Renumber, then number the children
- Subtract the level's first position from each node:
p = pos - first. - Give the left child
2pand the right child2p + 1.
Without renumbering, positions double every level and overflow 64-bit integers on a skewed tree about 64 levels deep. Shifting by first keeps every number below the level's width, and widths are unchanged because only differences are used.
Repeat until no level is left
The children, in order, form the next level. Keep going until a level comes back empty, then return best. Each node is queued exactly once, so this maximum width of binary tree solution is O(n) time and holds at most one level in memory.
Maximum Width of Binary Tree solution in Python | C++ | Java
Common pitfalls
Counting nodes instead of positions
best = max(best, len(level))
best = max(best, last - first + 1)
For [1, 3, 2, 5, null, null, 9] the last level has 2 nodes but width 4, because the two empty slots between 5 and 9 count.
Never renumbering the positions
nxt.append((node.left, 2 * pos))
p = pos - first nxt.append((node.left, 2 * p))
Positions double every level. On a skewed tree 3,000 levels deep they pass 2^3000; in C++ and Java that overflows long after about 63 levels and gives wrong widths.
Enqueueing null children
nxt.append((node.left, 2 * p)) nxt.append((node.right, 2 * p + 1))
if node.left:
nxt.append((node.left, 2 * p))
if node.right:
nxt.append((node.right, 2 * p + 1))Nulls at the ends would stretch the width past the real end nodes. The numbering already accounts for gaps, so only real nodes go in the level list.
Edge cases
In [1, 2, 3, 4, null, null, 5, 6] the third level has width 4 but the last holds only node 6. best is updated on every level, not just the last.
Complexity
Maximum Width of Binary Tree FAQ
What is the width of a binary tree level?
The number of positions from the leftmost to the rightmost non-null node on that level, counting the empty positions between them as if the level were full. For [1, 3, 2, 5, 3, null, 9] the last level 5, 3, _, 9 has width 4.
How do you calculate the maximum width of a binary tree?
- Index nodes: root 0; children of position
pare2pand2p + 1. - Traverse: BFS, one level at a time, storing
(node, position). - Measure: width = last position - first position + 1; keep the maximum.
- Avoid overflow: subtract the level's first position before numbering the children.
- Complexity: O(n) time, O(w) space.
- Example:
[1, 3, 2, 5, 3, null, 9]gives 4.
Why do the positions need to be renumbered?
Each level doubles the positions, so after k levels they reach about 2^k. With up to 3,000 levels that overflows any fixed-size integer. Subtracting the first position of the level keeps every number smaller than the level's width.
Can maximum width be solved with DFS?
Yes. Pass (depth, position) down the recursion and store the first position seen at each depth; at every node compute position - first[depth] + 1. It is also O(n), but BFS makes the level boundaries explicit.