Maximum Width of Binary Tree
Real-world version: Widest Trellis TierThe statement here is our own: the same inputs, outputs and technique.
A vine trellis is built in tiers. One plant sits at the top, and every plant may send a shoot down-left and a shoot down-right into the tier below it, so tier 0 has one slot, tier 1 has two slots, tier 2 has four, and so on. Slots with no shoot in them are simply empty.
The trellis arrives as trellis, a tier-by-tier listing. trellis[0] is the top plant's tag. The rest of the list is consumed two entries at a time, taking plants in the order they were listed: the next two entries are that plant's down-left and down-right tags, and null means that shoot is absent, so it contributes no entries of its own. Trailing nulls are omitted.
The width of a tier is the number of slots covered when you go from its leftmost filled slot to its rightmost filled slot inclusive; empty slots that lie between those two ends still count, because the framework holds them whether a shoot arrived or not.
Return the largest width over all tiers.
Examples
Example 1
- Input
- trellis = [3, 5, 8, 2, null, null, 7]
- Output
- 4
Tier 2 has plant 2 in its first slot and plant 7 in its fourth slot, with the two middle slots empty, so it covers four slots.
Example 2
- Input
- trellis = [1, 2, 3, 4, null, null, 5, 6, null, null, 7]
- Output
- 8
Tier 3 has plant 6 in its first slot and plant 7 in its eighth slot, so it covers eight slots.
Example 3
- Input
- trellis = [1, 2, null, 4]
- Output
- 1
Each tier holds a single plant, so no tier covers more than one slot.
Example 4
- Input
- trellis = [7]
- Output
- 1
The trellis is a single plant on tier 0.
Constraints
- The number of plants on the trellis is in the range [1, 3000].
- -100 <= plant tag <= 100
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def width_of_binary_tree(trellis: list) -> int:public int widthOfBinaryTree(Integer[] trellis)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 9 test cases: 9 passed
- Passed: 4 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's