DSA problem
Step-By-Step Directions From a Binary Tree Node to Another
You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given a starting node value startValue and a target node value destValue. Find the shortest path from the start node to the destination node and represent it as a string of directions where each character is 'L' (go to the left child), 'R' (go to the right child), or 'U' (go up to the parent).
The shortest path between two nodes in a tree always passes through their lowest common ancestor (LCA). Going via any other ancestor would force the path to climb above the LCA only to descend back below it, which is strictly longer. So the algorithm has two phases: first locate the LCA of startValue and destValue, then build the directions by going up from start to the LCA and down from the LCA to dest.
A clean trick avoids tracking the start-to-LCA path explicitly: build the LCA-to-start path of 'L'/'R' directions using a standard root-to-target search, then replace every character with 'U' — each step downward in that search becomes an upward step on the actual path. Concatenate that string with the LCA-to-dest path built the same way (but kept as 'L'/'R').
The whole computation runs in O(n) time: one LCA traversal plus two root-to-target searches, each O(n). The output string has length at most O(n), and the algorithm uses O(h) recursion stack space.
Examples
root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6"UURL"root = [2,1], startValue = 2, destValue = 1"L"root = [1,2], startValue = 2, destValue = 2""Constraints
- The number of nodes in the tree is n.
- 2 <= n <= 10^5
- 1 <= Node.val <= n
- All the values of the nodes are unique.
- 1 <= startValue, destValue <= n; startValue != destValue.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.