Step-By-Step Directions From a Binary Tree Node to Another
Step-By-Step Directions From a Binary Tree Node to Another is a medium trees & bst problem solved with the lca pattern.
The best approach, optimal (root paths + common prefix), runs in O(n) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (parent map + bfs) up.
Problem
You are given the root of a binary tree with n nodes, each holding a distinct value from 1 to n, and two values startValue and destValue.
Return the shortest sequence of moves that leads from the node with value startValue to the node with value destValue, as a string made of these 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.
Examples
Example 1
- Input
root = [5, 4, 6, 2, 7, null, 1, null, null, 3], startValue = 3, destValue = 1- Output
"UUURR"- Why
- From 3 go up to 7, up to 4, up to the root 5, then right to 6 and right again to 1.
Example 2
- Input
root = [2, 3, 1], startValue = 2, destValue = 3- Output
"L"- Why
- The destination is the left child of the start.
Example 3
- Input
root = [1, 2, null, 3, 4], startValue = 4, destValue = 3- Output
"UL"- Why
- Go up from 4 to their common parent 2, then down to its left child 3.
Constraints
- The number of nodes
nis in the range[2, 10^5] 1 <= Node.val <= n, and all values are distinctstartValueanddestValueare values of nodes in the treestartValue != destValue
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (parent map + BFS) | O(n) | O(n) |
| Optimal (root paths + common prefix) | O(n) | O(h) |
1Brute force (parent map + BFS)
O(n)Each node is visited a constant number of times by the parent pass and the BFS.O(n)Parent map, visited map and queue each hold up to n nodes. It needs several extra maps, which the optimal approach avoids.Treat the tree as an undirected graph. Record each node's parent, then run a BFS from the start node, moving to the left child ('L'), right child ('R') or parent ('U'). Remember how each node was first reached, and rebuild the direction string once the destination is popped.
- DFS/BFS from the root to record every node's parent and find the start node.
- BFS from the start; for each neighbour (left, right, parent) not yet seen, store (previous node, letter).
- When the destination is reached, walk the stored links back to the start, collecting letters.
- Reverse the letters and return them as a string.
class Solution {
public String getDirections(TreeNode root, int startValue, int destValue) {
Map<TreeNode, TreeNode> parent = new HashMap<>();
TreeNode start = null;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.val == startValue) start = node;
if (node.left != null) { parent.put(node.left, node); stack.push(node.left); }
if (node.right != null) { parent.put(node.right, node); stack.push(node.right); }
}
Map<TreeNode, TreeNode> from = new HashMap<>();
Map<TreeNode, Character> step = new HashMap<>();
from.put(start, null);
Deque<TreeNode> queue = new ArrayDeque<>();
queue.add(start);
TreeNode dest = null;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.val == destValue) { dest = node; break; }
TreeNode[] next = { node.left, node.right, parent.get(node) };
char[] letter = { 'L', 'R', 'U' };
for (int k = 0; k < 3; k++) {
if (next[k] != null && !from.containsKey(next[k])) {
from.put(next[k], node);
step.put(next[k], letter[k]);
queue.add(next[k]);
}
}
}
StringBuilder sb = new StringBuilder();
for (TreeNode cur = dest; cur != start; cur = from.get(cur)) sb.append(step.get(cur));
return sb.reverse().toString();
}
}class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
parent = {}
start = None
stack = [root]
while stack:
node = stack.pop()
if node.val == startValue:
start = node
for child in (node.left, node.right):
if child:
parent[child] = node
stack.append(child)
frm = {start: None}
step = {}
queue = deque([start])
dest = None
while queue:
node = queue.popleft()
if node.val == destValue:
dest = node
break
for nxt, letter in ((node.left, 'L'), (node.right, 'R'), (parent.get(node), 'U')):
if nxt is not None and nxt not in frm:
frm[nxt] = node
step[nxt] = letter
queue.append(nxt)
out = []
cur = dest
while cur is not start:
out.append(step[cur])
cur = frm[cur]
return ''.join(reversed(out))class Solution {
public:
string getDirections(TreeNode* root, int startValue, int destValue) {
unordered_map<TreeNode*, TreeNode*> parent;
TreeNode* start = nullptr;
vector<TreeNode*> stack = {root};
while (!stack.empty()) {
TreeNode* node = stack.back();
stack.pop_back();
if (node->val == startValue) start = node;
if (node->left) { parent[node->left] = node; stack.push_back(node->left); }
if (node->right) { parent[node->right] = node; stack.push_back(node->right); }
}
unordered_map<TreeNode*, TreeNode*> from;
unordered_map<TreeNode*, char> step;
from[start] = nullptr;
queue<TreeNode*> q;
q.push(start);
TreeNode* dest = nullptr;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node->val == destValue) { dest = node; break; }
TreeNode* up = parent.count(node) ? parent[node] : nullptr;
TreeNode* next[3] = {node->left, node->right, up};
char letter[3] = {'L', 'R', 'U'};
for (int k = 0; k < 3; k++) {
if (next[k] && !from.count(next[k])) {
from[next[k]] = node;
step[next[k]] = letter[k];
q.push(next[k]);
}
}
}
string out;
for (TreeNode* cur = dest; cur != start; cur = from[cur]) out += step[cur];
reverse(out.begin(), out.end());
return out;
}
};function getDirections(root, startValue, destValue) {
const parent = new Map();
let start = null;
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
if (node.val === startValue) start = node;
if (node.left) { parent.set(node.left, node); stack.push(node.left); }
if (node.right) { parent.set(node.right, node); stack.push(node.right); }
}
const from = new Map([[start, null]]);
const step = new Map();
const queue = [start];
let head = 0, dest = null;
while (head < queue.length) {
const node = queue[head++];
if (node.val === destValue) { dest = node; break; }
const next = [[node.left, 'L'], [node.right, 'R'], [parent.get(node) ?? null, 'U']];
for (const [nxt, letter] of next) {
if (nxt && !from.has(nxt)) {
from.set(nxt, node);
step.set(nxt, letter);
queue.push(nxt);
}
}
}
const out = [];
for (let cur = dest; cur !== start; cur = from.get(cur)) out.push(step.get(cur));
return out.reverse().join('');
}2Optimal (root paths + common prefix)
O(n)Each DFS visits every node at most once.O(h)The recursion stack and the path strings are bounded by the tree height h (up to n for a skewed tree).Record the path from the root to the start and from the root to the destination as strings of 'L' and 'R'. Their longest common prefix leads to the lowest common ancestor. Everything after that prefix on the start's path has to be climbed back up (one 'U' per letter), and everything after it on the destination's path is followed as-is.
- Find the root-to-start path and the root-to-destination path with a DFS that appends a letter going down and removes it when backtracking.
- Skip the common prefix of the two paths (length p).
- Answer = 'U' repeated (startPath.length - p) times + destPath.substring(p).
class Solution {
public String getDirections(TreeNode root, int startValue, int destValue) {
StringBuilder toStart = new StringBuilder(), toDest = new StringBuilder();
findPath(root, startValue, toStart);
findPath(root, destValue, toDest);
int p = 0;
while (p < toStart.length() && p < toDest.length() && toStart.charAt(p) == toDest.charAt(p)) p++;
StringBuilder sb = new StringBuilder();
for (int i = p; i < toStart.length(); i++) sb.append('U');
sb.append(toDest, p, toDest.length());
return sb.toString();
}
private 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;
}
}class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
def find_path(node: Optional[TreeNode], target: int, path: List[str]) -> bool:
if node is None:
return False
if node.val == target:
return True
path.append('L')
if find_path(node.left, target, path):
return True
path[-1] = 'R'
if find_path(node.right, target, path):
return True
path.pop()
return False
to_start, to_dest = [], []
find_path(root, startValue, to_start)
find_path(root, destValue, to_dest)
p = 0
while p < len(to_start) and p < len(to_dest) and to_start[p] == to_dest[p]:
p += 1
return 'U' * (len(to_start) - p) + ''.join(to_dest[p:])class Solution {
public:
string getDirections(TreeNode* root, int startValue, int destValue) {
string toStart, toDest;
findPath(root, startValue, toStart);
findPath(root, destValue, toDest);
size_t p = 0;
while (p < toStart.size() && p < toDest.size() && toStart[p] == toDest[p]) p++;
return string(toStart.size() - p, 'U') + toDest.substr(p);
}
private:
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;
}
};function getDirections(root, startValue, destValue) {
const findPath = (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;
};
const toStart = [], toDest = [];
findPath(root, startValue, toStart);
findPath(root, destValue, toDest);
let p = 0;
while (p < toStart.length && p < toDest.length && toStart[p] === toDest[p]) p++;
return 'U'.repeat(toStart.length - p) + toDest.slice(p).join('');
}Edge cases to test
- The destination is a descendant of the start (no 'U' at all)
- The start is a descendant of the destination (only 'U's)
- The two nodes are in different subtrees of the root
- A very deep, skewed tree
Hints
Hint 1
Any shortest path in a tree goes up from the start to the lowest common ancestor, then down to the destination.
Hint 2
Write down the root-to-node path (as 'L'/'R' letters) for both nodes. What does their common prefix represent?
Hint 3
Drop the common prefix; every remaining step on the start's path becomes 'U', followed by the rest of the destination's path.
FAQ
What is the best time complexity for Step-By-Step Directions From a Binary Tree Node to Another?
Optimal (root paths + common prefix) runs in O(n) time and O(h) extra space. Each DFS visits every node at most once.
Which pattern does Step-By-Step Directions From a Binary Tree Node to Another use?
It is a trees & bst problem that uses the lca pattern. Other problems with the same pattern: Lowest Common Ancestor of a Binary Tree, Lowest Common Ancestor of a Binary Search Tree, Smallest Common Region.
Is there a brute force solution for Step-By-Step Directions From a Binary Tree Node to Another?
Yes. Brute force (parent map + BFS) takes O(n) time and O(n) space. Treat the tree as an undirected graph.
Which edge cases should I test for Step-By-Step Directions From a Binary Tree Node to Another?
The destination is a descendant of the start (no 'U' at all); The start is a descendant of the destination (only 'U's); The two nodes are in different subtrees of the root; A very deep, skewed tree.