448. Maximum Width of Binary Tree
You are given the root of a binary tree. Every level of the tree has a width: locate the leftmost and the rightmost non-null nodes on that level, then count how many positions the level spans between them, inclusive — the empty slots a complete binary tree would reserve between those two nodes count toward the width too.
Return the largest width found on any level.
Think of positions the way a binary heap numbers them: a node at position i places its left child at 2i and its right child at 2i + 1. The width of a level is then rightmost position − leftmost position + 1.
The function receives the root node and returns one integer. The answer is guaranteed to fit in a 32-bit signed integer.
Example 1:
Input: root = [1, 3, 2, 5, 3, null, 9]
Output: 4
Explanation: The bottom level holds 5, 3 and 9 at positions 4, 5 and 7. Position 6 is an empty slot between 3 and 9, but it still counts, so the level spans 7 − 4 + 1 = 4 positions.
Example 2:
Input: root = [1, 2, 3, 4, null, null, 5]
Output: 4
Explanation: On the bottom level, 4 sits at the far left (position 4) and 5 at the far right (position 7). The two reserved slots between them are empty yet counted: 7 − 4 + 1 = 4.
Constraints:
- 1 ≤ number of nodes ≤ 3000
- -100 ≤ Node.val ≤ 100
- The answer fits in a 32-bit signed integer.
Hints:
Number every node the way a binary heap does: a node at position i has children at 2i and 2i + 1. A level's width is then simply rightmost − leftmost + 1 — the gaps in between account for themselves.
Positions double at every level, so a deep skinny tree can overflow even 64-bit integers. Re-base each level: subtract the level's leftmost position before computing children's positions. Every position on the level shifts by the same amount, so widths are unchanged.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 3, 2, 5, 3, null, 9]
Expected output: 4