Show problems as
Classic problem #2096MediumStringTreeDepth-First SearchBinary TreeBinary LiftingLowest Common Ancestor

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

Real-world version: Relay Route Between Two Stations
Tracked in this browser only
Read Step-By-Step Directions From a Binary Tree Node to Another on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard 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)

More on the same topics