Step-By-Step Directions From a Binary Tree Node to Another Solution
Step-By-Step Directions From a Binary Tree Node to Another solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Step-By-Step Directions From a Binary Tree Node to Another is a medium coding problem on strings, depth-first search and trees, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Strings, Depth-First Search, Trees
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree with n nodes whose values are the distinct integers 1 to n, and two different values startValue and destValue.
Return the directions for the shortest walk from the node holding startValue to the node holding destValue, as a string of the letters:
L— move to the current node's left child;R— move to the current node's right child;U— move to the current node's parent.
Example 1
Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: UURL
Explanation: From 3 go up to 1, up to 5, right to 2, left to 6.
Example 2
Input: root = [2,1], startValue = 2, destValue = 1
Output: L
Explanation: 1 is the left child of 2.
Example 3
Input: root = [1,2,3,4,5], startValue = 5, destValue = 4
Output: UL
Explanation: Up from 5 to their common parent 2, then left to 4.
Constraints
2 <= n <= 10^51 <= Node.val <= nall node values are distinct1 <= startValue, destValue <= nstartValue != destValue
Hints for Step-By-Step Directions From a Binary Tree Node to Another
Hint 1
The shortest walk goes up from the start to the lowest common ancestor of the two nodes, then down to the destination.
Hint 2
Write down the path from the root to each node as a string of
Ls andRs.Hint 3
The two strings share a prefix — the walk to the common ancestor. Drop it; every remaining step of the start's path becomes a
U, followed by the rest of the destination's path.
How to solve Step-By-Step Directions From a Binary Tree Node to Another
Both nodes hang off the root by an L/R path. Their longest common prefix leads to the lowest common ancestor; climbing from the start to it is one U per remaining start step, and the remaining destination steps lead down.
Approach
- Find the root-to-start path and the root-to-destination path as
L/Rstrings (depth-first search with backtracking). - Let
kbe the length of their longest common prefix. - Return
Urepeatedlen(startPath) - ktimes, followed bydestPath[k:].
Why it works
In a tree there is exactly one simple path between two nodes, and it passes through their lowest common ancestor — the last node shared by the two root paths, reached after exactly k common steps. From the start, len(startPath) - k parent moves reach it, and the destination's remaining steps lead down from there.
Complexity
- Time —
O(n) - Space —
O(n) for the paths and the recursion
Pitfalls
- Building path strings by concatenation at every call is quadratic — append to one buffer and backtrack.
- The common prefix must be compared step by step; do not try to compare node values along it.
Reference solution
Python
from typing import Optional
def getDirections(root: Optional[TreeNode], startValue: int, destValue: int) -> str:
def find(node, target, path):
if node is None:
return False
if node.val == target:
return True
path.append("L")
if find(node.left, target, path):
return True
path[-1] = "R"
if find(node.right, target, path):
return True
path.pop()
return False
ps, pd = [], []
find(root, startValue, ps)
find(root, destValue, pd)
k = 0
while k < len(ps) and k < len(pd) and ps[k] == pd[k]:
k += 1
return "U" * (len(ps) - k) + "".join(pd[k:])Java
public static String getDirections(TreeNode root, int startValue, int destValue) {
StringBuilder ps = new StringBuilder(), pd = new StringBuilder();
findPath(root, startValue, ps);
findPath(root, destValue, pd);
int k = 0;
while (k < ps.length() && k < pd.length() && ps.charAt(k) == pd.charAt(k)) k++;
StringBuilder out = new StringBuilder();
for (int i = k; i < ps.length(); i++) out.append('U');
out.append(pd, k, pd.length());
return out.toString();
}
static boolean findPath(TreeNode node, int target, StringBuilder path) {
if (node == null) return false;
if (node.val == target) return true;
path.append('L');
if (findPath(node.left, target, path)) return true;
path.setCharAt(path.length() - 1, 'R');
if (findPath(node.right, target, path)) return true;
path.deleteCharAt(path.length() - 1);
return false;
}C++
bool findPath(TreeNode* node, int target, string& path);
string getDirections(TreeNode* root, int startValue, int destValue) {
string ps, pd;
findPath(root, startValue, ps);
findPath(root, destValue, pd);
size_t k = 0;
while (k < ps.size() && k < pd.size() && ps[k] == pd[k]) k++;
return string(ps.size() - k, 'U') + pd.substr(k);
}
bool findPath(TreeNode* node, int target, string& path) {
if (!node) return false;
if (node->val == target) return true;
path.push_back('L');
if (findPath(node->left, target, path)) return true;
path.back() = 'R';
if (findPath(node->right, target, path)) return true;
path.pop_back();
return false;
}JavaScript
var getDirections = function(root, startValue, destValue) {
var ps = [], pd = [];
findPath(root, startValue, ps);
findPath(root, destValue, pd);
var k = 0;
while (k < ps.length && k < pd.length && ps[k] === pd[k]) k++;
var out = [];
for (var i = k; i < ps.length; i++) out.push("U");
for (var j = k; j < pd.length; j++) out.push(pd[j]);
return out.join("");
};
var findPath = function(node, target, path) {
if (node === null) return false;
if (node.val === target) return true;
path.push("L");
if (findPath(node.left, target, path)) return true;
path[path.length - 1] = "R";
if (findPath(node.right, target, path)) return true;
path.pop();
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Depth-First Search (DFS)