Step-By-Step Directions From a Binary Tree Node to Another
Medium · Trees · String · Tree · Depth-First Search · Binary Tree
Problem
You are given the root of a binary tree with n nodes whose values are exactly 1 to n, each used once, and two different values startValue and destValue.
Describe the shortest path from the start node to the destination node as a string of moves:
- 'L': go to the current node's left child,
- 'R': go to the current node's right child,
- 'U': go to the current node's parent.
Return that string.
Examples
Input: root = [4,1,6,3,None,2,5], startValue = 3, destValue = 5 Output: "UURR"
Climb from 3 to 1 to 4, then go right to 6 and right again to 5.
Input: root = [1,2], startValue = 1, destValue = 2 Output: "L"
The destination is the start's left child.
Input: root = [5,1,2,3,None,6,4], startValue = 4, destValue = 5 Output: "UU"
4 is the right child of 2, which is the right child of 5: two steps up.
Constraints
- The tree has n nodes, 2 <= n <= 10^5
- 1 <= Node.val <= n, all values distinct
- 1 <= startValue, destValue <= n
- startValue != destValue
Approaches
- Baseline: climb until the destination is below — time O(n · h), space O(n)
Follow-up
The route is unique: a tree has exactly one simple path between two nodes, so there is only one shortest move string. For many queries on the same tree, store each node's depth and use binary lifting to find common ancestors in O(log n) per query.
Related problems
Start free on Cariara · Coding problems · System design studio
