Maximum Width of Binary Tree
Medium · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree, return the maximum width over all of its levels.
The width of a level is measured between its leftmost and rightmost nodes, counting the missing positions in between as if the level belonged to a complete binary tree. Missing positions outside those two end nodes do not count.
The answer fits in a 32-bit signed integer, but the positions themselves may not: a tree 3,000 levels deep numbers its bottom positions near 2^3000. The tests build trees with from_level([...]), a level-order list where None marks a missing child.
Examples
Input: root = [1,2,3,4,null,null,5] Output: 4
On the bottom level, 4 is in position 0 and 5 in position 3, with two empty positions between them.
Input: root = [1,2,null,3,4] Output: 2
The widest level is 3, 4.
Constraints
- 1 <= number of nodes <= 3000
- -100 <= Node.val <= 100
- the answer fits in a 32-bit signed integer
Approaches
- Baseline: lay out every position, gaps included — time O(sum of the widths), space O(maximum width)
Follow-up
What if you measured columns instead of positions, with a left child one column left and a right child one column right? Then a single walk tracking the smallest and largest column is enough (see the use case “How many columns the tree spans”).
Related problems
Start free on Cariara · Coding problems · System design studio
