Minimum Depth of Binary Tree
Real-world version: Shortest Route to a Terminal BoxThe statement here is our own: the same inputs, outputs and technique.
An approval workflow is drawn as a binary flowchart. Each box carries a signed number and has at most two follow-on boxes, one drawn to its left and one to its right. A box with no follow-on on either side is a terminal box.
The chart arrives as chart, a level-by-level listing. chart[0] is the entry box. After that, every box already listed contributes two entries in turn, its left follow-on then its right follow-on, with null where that follow-on is missing. A null contributes nothing further, and null entries at the very end of the listing are left off. An empty listing means there is no chart at all.
A route runs from the entry box down through follow-on boxes, and its length is the number of boxes on it, the entry box counted. Return the length of the shortest route that ends at a terminal box, or 0 when the listing is empty.
Examples
Example 1
- Input
- chart = [8, 4, 12, null, 6]
- Output
- 2
Box 12 is a follow-on of the entry box and has no follow-on of its own, so the route entry box then 12 counts two boxes.
Example 2
- Input
- chart = [1, null, 2, null, 3]
- Output
- 3
The chart is a single line of three boxes, and the third of them is the first one on that line with no follow-on.
Example 3
- Input
- chart = []
- Output
- 0
The listing is empty, so there is no chart and the answer is 0.
Constraints
- The number of boxes in the chart is in the range [0, 10^5].
- -1000 <= box value <= 1000
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 shortest_route_to_terminal(chart: list[int | None]) -> int:public int shortestRouteToTerminal(Integer[] chart)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 9 test cases: 9 passed
- Passed: 3 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