Maximum Width Of Binary Tree
01 · Problem
Given the root of a binary tree, return the maximum width across all of its levels.
The width of a level is the number of positions from its leftmost non-null node to its rightmost non-null node, inclusive, counting the null gaps in between as if the level belonged to a complete binary tree. Positions beyond the outermost real nodes are not counted. A level with a single node has width 1. The tree is given in level-order form, with null marking missing children.
The answer is guaranteed to fit in a 32-bit signed integer.
02 · Examples
root = [1,3,2,5,3,null,9]
4
The last level holds 5, 3, a gap, and 9, so it spans 4 positions.
root = [1,3,2,5,null,null,9,6,null,7]
7
The bottom level has 6 at the far left and 7 at the far right, with five empty positions between them, for a width of 7.
root = [1,3,2,5]
2
The second level contains 3 and 2 (width 2); the bottom level contains only 5 (width 1).
03 · Constraints
- 01The number of nodes in the tree is in the range [1, 3000].
- 02-100 <= Node.val <= 100
- 03The answer fits in a 32-bit signed integer.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.