0330MediumStringTreeDepth-First SearchBinary TreeBinary LiftingLowest Common Ancestor

Relay Route Between Two Stations

Tracked in this browser only

Trains the technique from

LeetCode 2096Step-By-Step Directions From a Binary Tree Node to Another

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.

A courier network is wired as a binary tree of relay stations. Every station carries a distinct id, and each station has an optional left downstream station and an optional right downstream station.

How the tree arrives. The argument root is handed over as a flat array in breadth-first order. Entry 0 is the id at the top of the network. After that, for each station in the order it is reached, the array holds its left slot and then its right slot, using null for a slot with nothing wired into it. An empty slot has no slots of its own. null entries at the very end of the array are omitted.

A courier standing at a station can make one of three moves: 'U' hands the parcel up to the station directly above, 'L' hands it down into the left slot, and 'R' hands it down into the right slot.

Return the move sequence, as a string, that carries a parcel from the station with id startValue to the station with id destValue using as few moves as possible.

Examples

Example 1

Input: root = [5, 1, 4, 3, 6, 2, 7], startValue = 6, destValue = 2
Output: "UURL"

Station 6 hangs under 1, which hangs under 5; station 2 is the left slot of 4, which is the right slot of 5. The route 6 -> 1 -> 5 -> 4 -> 2 spells UURL.

Example 2

Input: root = [5, 1, 4, 3, 6, 2, 7], startValue = 3, destValue = 1
Output: "U"

Station 3 sits directly under station 1, so a single upward hand-off finishes the job.

Example 3

Input: root = [1, null, 2, null, 3], startValue = 1, destValue = 3
Output: "RR"

The network is a right-leaning chain 1 -> 2 -> 3, so the parcel goes down the right slot twice.

Example 4

Input: root = [4, 2, 6, 1, 3, null, 5], startValue = 5, destValue = 3
Output: "UULR"

Station 5 hangs in the right slot of 6, and 6 in the right slot of 4; station 3 is the right slot of 2, which is the left slot of 4. The route 5 -> 6 -> 4 -> 2 -> 3 spells UULR.

Constraints

The number of stations in the tree is n.
2 <= n <= 10^5
1 <= station id <= n
Every station id is distinct.
1 <= startValue, destValue <= n
startValue != destValue

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 relay_route(tree: list, from_label: int, to_label: int) -> str:

Java

public String relayRoute(Integer[] tree, int fromLabel, int toLabel)

The intended approach

Time O(n)Space O(n)

Rebuild the network from the flat array into parent links, remembering for each station whether it hangs in its parent's left or right slot. Climb from each of the two stations up to the top, which gives the two top-down move lists; the moves they share at the front lead to the deepest station both routes pass through. Everything left over on the start side becomes upward hand-offs and everything left over on the destination side is appended unchanged. Both climbs are plain loops, so a chain of 10^5 stations is fine.

Pythonentry point: relay_route

def relay_route(tree, from_label, to_label):
    # Rebuild the tree as parent links, then climb from both stations to the
    # root and drop the shared tail of the two climbs. No recursion at all, so a
    # long thin tree is safe.
    # Time O(n). Space O(n).
    labels = [tree[0]]
    kids = [[-1, -1]]
    order = [0]
    head = 0
    i = 1
    while head < len(order):
        u = order[head]
        head += 1
        for slot in (0, 1):
            if i >= len(tree):
                break
            v = tree[i]
            i += 1
            if v is not None:
                labels.append(v)
                kids.append([-1, -1])
                idx = len(labels) - 1
                kids[u][slot] = idx
                order.append(idx)
    where = {}
    for idx, lab in enumerate(labels):
        where[lab] = idx
    up = [-1] * len(labels)
    step = [""] * len(labels)
    for u in range(len(labels)):
        for slot, mark in ((0, "L"), (1, "R")):
            c = kids[u][slot]
            if c != -1:
                up[c] = u
                step[c] = mark
    def climb(node):
        moves = []
        while up[node] != -1:
            moves.append(step[node])
            node = up[node]
        moves.reverse()
        return moves
    a = climb(where[from_label])
    b = climb(where[to_label])
    shared = 0
    limit = min(len(a), len(b))
    while shared < limit and a[shared] == b[shared]:
        shared += 1
    return "U" * (len(a) - shared) + "".join(b[shared:])

The obvious version

Rebuild the network as an undirected graph whose edges carry their move letter, run a breadth-first search from the start station, then read the move letters back along the recorded predecessors.

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_relay_route(tree, from_label, to_label):
    from collections import deque
    labels = [tree[0]]
    kids = [[-1, -1]]
    order = [0]
    head = 0
    i = 1
    while head < len(order):
        u = order[head]
        head += 1
        for slot in (0, 1):
            if i >= len(tree):
                break
            v = tree[i]
            i += 1
            if v is not None:
                labels.append(v)
                kids.append([-1, -1])
                idx = len(labels) - 1
                kids[u][slot] = idx
                order.append(idx)
    adj = [[] for _ in labels]
    for u in range(len(labels)):
        for slot, mark in ((0, "L"), (1, "R")):
            c = kids[u][slot]
            if c != -1:
                adj[u].append((c, mark))
                adj[c].append((u, "U"))
    src = labels.index(from_label)
    dst = labels.index(to_label)
    prev = {src: None}
    q = deque([src])
    while q:
        u = q.popleft()
        if u == dst:
            break
        for v, mark in adj[u]:
            if v not in prev:
                prev[v] = (u, mark)
                q.append(v)
    out = []
    cur = dst
    while prev[cur] is not None:
        u, mark = prev[cur]
        out.append(mark)
        cur = u
    out.reverse()
    return "".join(out)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
4 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