Widest Level of the Tree, Counting the Gaps
Implement widestLevel
You are given the root of a binary tree. The width of a level is the distance between its leftmost and rightmost nodes, where the empty positions between them are counted too. To make "positions" precise, imagine every node has two child slots, as in a perfect binary tree; the width is the number of slots from the leftmost real node to the rightmost real node, inclusive. Return the largest width over all levels of the tree.
Building every level with explicit empty slots is easy but can explode in size. Numbering the slots (a node in slot s has children in slots 2s and 2s + 1) gives the width from just two numbers per level.
Example 1:
Input: root = [8,5,12,2,null,null,15,1,null,null,20]
Output: 8
Example 2:
Input: root = [4,2,7,1,null,null,9]
Output: 4
Example 3:
Input: root = [1]
Output: 1
+ 13 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100; −100 ≤ node.val ≤ 100 (values never affect the answer) - ●
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ●
The width of a level is the distance from its leftmost node to its rightmost node, counting the empty positions in between, where every node is imagined to have two child slots (as in a complete binary tree). Return the largest width over all levels (0 for an empty tree) - ●
The answer is guaranteed to fit in a signed 32-bit integer; use a wider type for intermediate positions
root =