Widest Floor
MediumTrees
Problem
Imagine the binary tree drawn inside a complete binary tree of the same height, so every level has a fixed number of slots. The width of a level is the number of slots from its leftmost existing node to its rightmost existing node, inclusive, counting empty slots in between.
Given the root of a non-empty tree, return the maximum width over all levels. The answer fits in a signed 32-bit integer.
Example 1
- Input:
- root = [1, 3, 2, 5, 3, null, 9]
- Output:
- 4
Level 3 runs from 5 to 9 across four slots: 5, 3, (empty), 9.
Example 2
- Input:
- root = [1, 3, 2, 5, null, null, 9, 6, null, 7]
- Output:
- 7
Level 4 runs from 6 (far left) to 7 (far right): 7 slots.
Example 3
- Input:
- root = [1, 3, 2, 5]
- Output:
- 2
Constraints
- 1 ≤ number of nodes ≤ 3000
- -100 ≤ node.val ≤ 100
- The answer fits in a signed 32-bit integer.
Hint
Show the first hint
Give each node a position number as in an array-backed heap: the root is 0, the children of p are 2p and 2p + 1.
Walkthrough
How to approach it
01Clarify before coding
- Do empty slots between nodes count? Yes, but only between the two extremes of a level.
- Empty slots below a missing node also count? Yes, the slots exist as if the tree were complete.
- How large can positions get? A chain of 100 nodes would need 2^100 without care, so we must keep numbers small.
02Brute force
Materialise every level as a list of slots with null placeholders and trim the ends.
Cost: Exponential: level k has 2^k slots, impossible for deep sparse trees.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.