Compute the maximum width among all levels of a binary tree, counting the gaps between the leftmost and rightmost non-null nodes.
Maximum Width of Binary Tree
Given the root of a binary tree, determine the maximum width across all levels.
For a given level, the width is measured from the position of the leftmost non-null node to the position of the rightmost non-null node, including any missing nodes in between. Treat the tree as if it were embedded in a complete binary tree so that nodes on each level can be assigned positions.
Return the largest width over all levels.
Notes
- A level may contain sparse nodes separated by nulls.
- The width is not just the count of actual nodes on the level; it includes the space between the outermost nodes.
Input Format
- The input is the root of a binary tree.
- Each node contains an integer value and pointers to left and right children.
Output Format
- Return a single integer: the maximum width across all tree levels.
Constraints
- The tree contains at least one node.
- The number of nodes is finite.
- Node values are irrelevant to the width calculation.
- A level may be very sparse, so position tracking should avoid losing relative spacing.
Example 1
Input
root = [1,3,2,5,3,null,9]
Output
4
Explanation
At the last level, the leftmost node is at position 0 and the rightmost node is at position 3, so the width is 4.
Example 2
Input
root = [1,3,2,5,null,null,9,6,null,null,7]
Output
7
Explanation
The widest level spans from the leftmost to rightmost occupied positions across several gaps, giving a width of 7.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.