0280EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Shortest Route to a Terminal Box

Tracked in this browser only

Trains the technique from

LeetCode 111Minimum Depth of Binary Tree

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def shortest_route_to_terminal(chart: list[int | None]) -> int:

Java

public int shortestRouteToTerminal(Integer[] chart)

The intended approach

Time O(n)Space O(n)

First turn the level-order listing into two child index tables by handing out consecutive entries to the boxes in the order they are discovered. Then sweep the chart one level at a time, building the next level from the follow-ons of the current one, and return the current length as soon as a box on this level has no follow-on on either side. Both stages run off explicit queues, so a chart drawn as one long chain does not recurse.

Pythonentry point: shortest_route_to_terminal

def shortest_route_to_terminal(chart):
    # Two explicit queues and no recursion, so a chart shaped as one long chain of
    # 100000 boxes is safe.  First the level-order listing is turned into child
    # index tables, then the boxes are visited level by level and the walk stops at
    # the first box with no follow-on, which lies on the shallowest such level.
    # Time: O(n).  Space: O(n) for the child tables and the level queues.
    if not chart or chart[0] is None:
        return 0
    n = len(chart)
    left = [-1] * n
    right = [-1] * n
    order = [0]
    head = 0
    i = 1
    while head < len(order) and i < n:
        node = order[head]
        head += 1
        if i < n:
            if chart[i] is not None:
                left[node] = i
                order.append(i)
            i += 1
        if i < n:
            if chart[i] is not None:
                right[node] = i
                order.append(i)
            i += 1
    level = [0]
    length = 1
    while level:
        nxt = []
        for node in level:
            if left[node] < 0 and right[node] < 0:
                return length
            if left[node] >= 0:
                nxt.append(left[node])
            if right[node] >= 0:
                nxt.append(right[node])
        level = nxt
        length += 1
    return length

The obvious version

Rebuild the chart as linked dictionaries, then walk every route from the entry box with an explicit stack, recording the length of each route that reaches a terminal box, and take the smallest.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_shortest_route_to_terminal(chart):
    if not chart or chart[0] is None:
        return 0
    boxes = [None if v is None else {"L": None, "R": None} for v in chart]
    pending = [boxes[0]]
    at = 0
    idx = 1
    while at < len(pending) and idx < len(chart):
        cur = pending[at]
        at += 1
        for side in ("L", "R"):
            if idx >= len(chart):
                break
            child = boxes[idx]
            idx += 1
            if child is not None:
                cur[side] = child
                pending.append(child)
    lengths = []
    stack = [(boxes[0], 1)]
    while stack:
        box, d = stack.pop()
        if box["L"] is None and box["R"] is None:
            lengths.append(d)
            continue
        if box["L"] is not None:
            stack.append((box["L"], d + 1))
        if box["R"] is not None:
            stack.append((box["R"], d + 1))
    return min(lengths)

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in