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 an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.
Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:
'L' means to go from a node to its left child node.'R' means to go from a node to its right child node.'U' means to go from a node to its parent node.Return the step-by-step directions of the shortest path from node s to node t.
Example 1:
Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6 Output: "UURL" Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.
Example 2:
Input: root = [2,1], startValue = 2, destValue = 1 Output: "L" Explanation: The shortest path is: 2 → 1.
Constraints:
n.2 <= n <= 1051 <= Node.val <= n1 <= startValue, destValue <= nstartValue != destValueTo solve #2096 Step-By-Step Directions From a Binary Tree Node to Another, the key idea is to identify the relationship between the startValue and destValue nodes in the binary tree. A common strategy is to first locate their Lowest Common Ancestor (LCA). The LCA represents the node where the paths to both target nodes diverge.
Using Depth-First Search (DFS), you can find the path from the root to each node and then determine the LCA by comparing these paths. Once the LCA is known, construct the final directions by moving U (up) from the start node to the LCA and then following L or R directions from the LCA to reach the destination node.
This approach works efficiently because each node is visited at most once during traversal. With careful path tracking and string construction, the algorithm achieves O(n) time complexity while using additional space for recursion and path storage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Lowest Common Ancestor and Path Construction | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
The shortest path between any two nodes in a tree must pass through their Lowest Common Ancestor (LCA). The path will travel upwards from node s to the LCA and then downwards from the LCA to node t.
Find the path strings from root → s, and root → t. Can you use these two strings to prepare the final answer?
Remove the longest common prefix of the two path strings to get the path LCA → s, and LCA → t. Each step in the path of LCA → s should be reversed as 'U'.
This approach involves finding the path from the start node to the root and the destination node to the root. Using these paths, the Lowest Common Ancestor (LCA) of the start and destination nodes is determined. This allows us to break down the path from start to destination as moving up towards the root to the LCA, then down towards the destination. Once these steps are identified, we can replace moves with correct directions ('L', 'R', 'U').
Time Complexity: O(n), where n is the number of nodes, as each node could be traversed in the worst-case.
Space Complexity: O(h), where h is the height of the tree due to recursion stack and storing paths.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7
8 TreeNode(int x) {
9 val = x;
10 left = null;
11 right = null;
12 }
13}
14
15public class Solution {
16 private boolean pathToNode(TreeNode root, int value, List<Character> path) {
17 if (root == null) return false;
18 if (root.val == value) return true;
19
20 path.add('L');
21 if (pathToNode(root.left, value, path)) return true;
22 path.remove(path.size() - 1);
23
24 path.add('R');
25 if (pathToNode(root.right, value, path)) return true;
26 path.remove(path.size() - 1);
27
28 return false;
29 }
30
31 public String getDirections(TreeNode root, int startValue, int destValue) {
32 List<Character> startPath = new ArrayList<>();
33 List<Character> destPath = new ArrayList<>();
34
35 pathToNode(root, startValue, startPath);
36 pathToNode(root, destValue, destPath);
37
38 int i = 0;
39 while (i < startPath.size() && i < destPath.size() && startPath.get(i) == destPath.get(i)) i++;
40 StringBuilder sb = new StringBuilder();
41
42 for (int j = i; j < startPath.size(); j++) {
43 sb.append('U');
44 }
45 for (int j = i; j < destPath.size(); j++) {
46 sb.append(destPath.get(j));
47 }
48
49 return sb.toString();
50 }
51
52 public static void main(String[] args) {
53 TreeNode root = new TreeNode(5);
54 root.left = new TreeNode(1);
55 root.right = new TreeNode(2);
56 root.left.left = new TreeNode(3);
57 root.right.left = new TreeNode(6);
58 root.right.right = new TreeNode(4);
59
60 Solution sol = new Solution();
61 System.out.println(sol.getDirections(root, 3, 6)); // Output: "UURL"
62 }
63}The Java solution mirrors the logic of the Python and C++ implementations. It uses a recursive helper method to determine paths to the specified nodes and then constructs the necessary direction steps. The solution accounts for shared path segments leading to the lowest common ancestor.
This approach uses a DFS to build a parent map of nodes first. With this map, we can easily track the movement from any node to any other node. We then extract paths from startValue and destValue up to a common ancestor. The directions are computed through knowledge of parent-child relationships and mapped accordingly using 'L', 'R', and 'U'.
Time Complexity: O(n), traversing all nodes for setup. Space Complexity: O(n) due to the parent mapping.
1using System;
2using System.Collections.Generic;
3
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private Dictionary<int, TreeNode> parentMap = new Dictionary<int, TreeNode>();
private void DFS(TreeNode node, TreeNode parent) {
if (node == null) return;
parentMap[node.val] = parent;
DFS(node.left, node);
DFS(node.right, node);
}
private List<char> GetPath(int value) {
List<char> path = new List<char>();
while (parentMap.ContainsKey(value) && parentMap[value] != null) {
TreeNode parent = parentMap[value];
if (parent.left != null && parent.left.val == value) {
path.Add('L');
} else if (parent.right != null && parent.right.val == value) {
path.Add('R');
}
value = parent.val;
}
path.Reverse();
return path;
}
public string GetDirections(TreeNode root, int startValue, int destValue) {
DFS(root, null);
List<char> startPath = GetPath(startValue);
List<char> destPath = GetPath(destValue);
int i = 0;
while (i < startPath.Count && i < destPath.Count && startPath[i] == destPath[i]) {
i++;
}
return new string('U', startPath.Count - i) + string.Concat(destPath.GetRange(i, destPath.Count - i));
}
public static void Main(string[] args) {
TreeNode root = new TreeNode(5);
root.left = new TreeNode(1);
root.right = new TreeNode(2);
root.left.left = new TreeNode(3);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(4);
Solution sol = new Solution();
Console.WriteLine(sol.GetDirections(root, 3, 6)); // Output: "UURL"
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The LCA helps separate the path into two segments: moving up from the start node and then moving down to the destination node. This avoids unnecessary traversal and simplifies constructing the final direction string.
Yes, similar binary tree path and Lowest Common Ancestor problems frequently appear in FAANG-style interviews. They test understanding of tree traversal, recursion, and path construction logic.
A binary tree combined with recursion or a stack for depth-first search works best. Additionally, strings or lists are used to store the path directions from the root or LCA to the target nodes.
The optimal approach is to find the Lowest Common Ancestor (LCA) of the start and destination nodes. From the start node you move up to the LCA using 'U', and then follow the path from the LCA to the destination using 'L' or 'R'. This can be implemented efficiently using depth-first search.
This C# implementation employs DFS to build a dictionary representing parent relationships, similar to the Python solution. It calculates paths from start and destination nodes up to their most recent common ancestor and uses these details to derive instructions for the needed path using 'L', 'R', and 'U'.