Step-By-Step Directions From a Binary Tree Node to Another solution and explanation
Google
9 more videos on this problem
Step-By-Step Directions from a Binary Tree Node to Another - Leetcode 2096 - PythonNeetCodeIO · 16:50 · 15K views
Step-By-Step Directions From a Binary Tree Node to Another | 2 Approaches | Leetcode 2096codestorywithMIK · 34:05 · 13K views
STEP-BY-STEP DIRECTIONS FROM A BINARY TREE NODE TO ANOTHER | PYTHON | LEETCODE # 2096Cracking FAANG · 18:50 · 9K views
2096. Step-By-Step Directions From a Binary Tree Node to Another | LCA | Backtracking | 2 PointersAryan Mittal · 15:13 · 6K views
Leetcode 2096 | Step-By-Step Directions From a Binary Tree Node to AnotherMike the Coder · 26:28 · 1K views
2096. Step-By-Step Directions From a Binary Tree Node to Another (Leetcode Medium)Programming Live with Larry · 15:38 · 1K views
Step By Step Directions From a Binary Tree Node to Another | Leetcode 2096 | Google高頻題 | Python今天比昨天厲害 · 23:42 · 686 views
Leetcode 2096 Step By Step Directions From a Binary Tree Node to AnotherMath Geeks · 12:37 · 275 views
Step-By-Step Directions From a Binary Tree Node to Another | Leetcode 2096 | Must do DSA questionsCode Thoughts · 14:37 · 184 views
Solve LeetCode - 2096. Step-By-Step Directions From a Binary Tree Node to AnotherMayur Programming Club · 24:05 · 157 views
The problem
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:
- The number of nodes in the tree is
n. 2 <= n <= 1051 <= Node.val <= n- All the values in the tree are unique.
1 <= startValue, destValue <= nstartValue != destValue
Approach overview
Problem Overview: You are given a binary tree and two node values: startValue and destValue. The task is to return a string describing the directions to move from the start node to the destination node. Moves are encoded as L (left child), R (right child), and U (parent).
Approach 1: Find Paths to Root and Compute Directions (O(n) time, O(n) space)
This method finds the path from the root to both startValue and destValue using a DFS traversal. Each path records moves (L or R). Once both paths are found, iterate from the start of both arrays to locate the lowest common ancestor (LCA) where the paths diverge. For every remaining step in the start path, append U. Then append the remaining moves from the destination path. This approach works because the path from start to destination always goes up to the LCA and then down to the target. It relies heavily on recursive traversal of a binary tree using depth-first search.
Approach 2: Using Depth-First Search (DFS) to Build Parent Map (O(n) time, O(n) space)
Another strategy treats the tree like an undirected graph. Run a DFS to build a parent map for each node while also tracking whether the node is a left or right child. Once this structure is ready, perform a DFS or BFS starting from startValue. From any node you can move left, right, or up to the parent. Track visited nodes and accumulate direction characters (L, R, U) until destValue is reached. This approach is flexible because it converts the tree into a graph traversal problem and explores neighbors directly.
Recommended for interviews: The path comparison approach is typically expected. It clearly shows understanding of tree traversal and the concept of the lowest common ancestor. Building a parent map and exploring like a graph also works in O(n) time but uses a slightly heavier structure. Interviewers usually prefer the LCA-style path solution because the reasoning is simpler and the resulting code is shorter.
Approach 1: Find Paths to Root and Compute Directions
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').
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def get_directions(self, startValue, destValue):
def path_to_node(root, value, path):
if not root:
return False
if root.val == value:
return True
path.append('L')
if path_to_node(root.left, value, path):
return True
path.pop()
path.append('R')
if path_to_node(root.right, value, path):
return True
path.pop()
return False
start_path, dest_path = [], []
path_to_node(self, startValue, start_path)
path_to_node(self, destValue, dest_path)
i = 0
while i < len(start_path) and i < len(dest_path) and start_path[i] == dest_path[i]:
i += 1
return 'U' * (len(start_path) - i) + ''.join(dest_path[i:])
# Example usage:
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(4)
print(root.get_directions(3, 6)) # Output: "UURL"import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
left = null;
right = null;
}
}
public class Solution {
private boolean pathToNode(TreeNode root, int value, List<Character> path) {
if (root == null) return false;
if (root.val == value) return true;
path.add('L');
if (pathToNode(root.left, value, path)) return true;
path.remove(path.size() - 1);
path.add('R');
if (pathToNode(root.right, value, path)) return true;
path.remove(path.size() - 1);
return false;
}
public String getDirections(TreeNode root, int startValue, int destValue) {
List<Character> startPath = new ArrayList<>();
List<Character> destPath = new ArrayList<>();
pathToNode(root, startValue, startPath);
pathToNode(root, destValue, destPath);
int i = 0;
while (i < startPath.size() && i < destPath.size() && startPath.get(i) == destPath.get(i)) i++;
StringBuilder sb = new StringBuilder();
for (int j = i; j < startPath.size(); j++) {
sb.append('U');
}
for (int j = i; j < destPath.size(); j++) {
sb.append(destPath.get(j));
}
return sb.toString();
}
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();
System.out.println(sol.getDirections(root, 3, 6)); // Output: "UURL"
}
}#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool pathToNode(TreeNode* root, int value, vector<char>& path) {
if (!root) return false;
if (root->val == value) return true;
path.push_back('L');
if (pathToNode(root->left, value, path)) return true;
path.pop_back();
path.push_back('R');
if (pathToNode(root->right, value, path)) return true;
path.pop_back();
return false;
}
string getDirections(TreeNode* root, int startValue, int destValue) {
vector<char> startPath, destPath;
pathToNode(root, startValue, startPath);
pathToNode(root, destValue, destPath);
int i = 0;
while (i < startPath.size() && i < destPath.size() && startPath[i] == destPath[i]) i++;
return string(startPath.size() - i, 'U') + string(destPath.begin() + i, destPath.end());
}
int main() {
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);
cout << getDirections(root, 3, 6) << endl; // Output: "UURL"
return 0;
}The code defines a TreeNode class with a method get_directions that computes the shortest path between two nodes in the form of directions. It uses a helper function path_to_node to traverse from the root to the specific node, appending 'L' or 'R' to a path list and returning True when the node is found. The main function finds paths to both start and destination nodes and calculates the direction by comparing the path steps. The paths are adjusted to determine when to move up and the remaining path to take.
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.
Approach 2: Using Depth-First Search (DFS) to Build Parent Map
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'.
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def get_directions(self, startValue, destValue):
parent_map = {}
def dfs(node, parent):
if not node:
return
parent_map[node.val] = parent
dfs(node.left, node)
dfs(node.right, node)
dfs(self, None)
def get_path(value):
path = []
while value in parent_map:
parent = parent_map[value]
if parent:
if parent.left and parent.left.val == value:
path.append('L')
elif parent.right and parent.right.val == value:
path.append('R')
value = parent.val if parent else None
return path[::-1]
start_path = get_path(startValue)
dest_path = get_path(destValue)
i = 0
while i < len(start_path) and i < len(dest_path) and start_path[i] == dest_path[i]:
i += 1
steps = 'U' * (len(start_path) - i) + ''.join(dest_path[i:])
return steps
# Example usage:
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(4)
print(root.get_directions(3, 6)) # Output: "UURL"class TreeNode {
constructor(val) {
this.val = val;
this.left = this.right = null;
}
}
function findDirections(root, startValue, destValue) {
const parentMap = new Map();
const dfs = (node, parent) => {
if (!node) return;
parentMap.set(node.val, parent);
dfs(node.left, node);
dfs(node.right, node);
};
dfs(root, null);
const getPath = (value) => {
const path = [];
while (parentMap.has(value) && parentMap.get(value)) {
const parent = parentMap.get(value);
if (parent.left && parent.left.val === value) {
path.push('L');
} else if (parent.right && parent.right.val === value) {
path.push('R');
}
value = parent.val;
}
return path.reverse();
};
const startPath = getPath(startValue);
const destPath = getPath(destValue);
let i = 0;
while (i < startPath.length && i < destPath.length && startPath[i] === destPath[i]) {
i++;
}
const steps = 'U'.repeat(startPath.length - i) + destPath.slice(i).join('');
return steps;
}
// Example usage
const 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);
console.log(findDirections(root, 3, 6)); // Output: "UURL"using System;
using System.Collections.Generic;
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"
}
}This solution creates a map of parent nodes using a depth-first search traversal. Once the parent map is available, the method accumulates paths from start and destination nodes to the root by tracking their parent relationships. Both paths are assessed for shared parent nodes to identify the LCA depth. The excess upward steps in the start path are marked with 'U', and further navigation from the LCA to the destination is indicated by the recorded 'L'/'R' movements.
Time Complexity: O(n), traversing all nodes for setup.
Space Complexity: O(n) due to the parent mapping.
Approach 3: Lowest Common Ancestor + DFS
We can first find the lowest common ancestor of nodes startValue and destValue, denoted as node. Then, starting from node, we find the paths to startValue and destValue respectively. The path from startValue to node will consist of a number of Us, and the path from node to destValue will be the path. Finally, we concatenate these two paths.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getDirections(root: TreeNode | null, startValue: number, destValue: number): string {
const lca = (node: TreeNode | null, p: number, q: number): TreeNode | null => {
if (node === null || [p, q].includes(node.val)) {
return node;
}
const left = lca(node.left, p, q);
const right = lca(node.right, p, q);
return left && right ? node : (left ?? right);
};
const dfs = (node: TreeNode | null, x: number, path: string[]): boolean => {
if (node === null) {
return false;
}
if (node.val === x) {
return true;
}
path.push('L');
if (dfs(node.left, x, path)) {
return true;
}
path[path.length - 1] = 'R';
if (dfs(node.right, x, path)) {
return true;
}
path.pop();
return false;
};
const node = lca(root, startValue, destValue);
const pathToStart: string[] = [];
const pathToDest: string[] = [];
dfs(node, startValue, pathToStart);
dfs(node, destValue, pathToDest);
return 'U'.repeat(pathToStart.length) + pathToDest.join('');
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getDirections(root *TreeNode, startValue int, destValue int) string {
var lca func(node *TreeNode, p, q int) *TreeNode
lca = func(node *TreeNode, p, q int) *TreeNode {
if node == nil || node.Val == p || node.Val == q {
return node
}
left := lca(node.Left, p, q)
right := lca(node.Right, p, q)
if left != nil && right != nil {
return node
}
if left != nil {
return left
}
return right
}
var dfs func(node *TreeNode, x int, path *[]byte) bool
dfs = func(node *TreeNode, x int, path *[]byte) bool {
if node == nil {
return false
}
if node.Val == x {
return true
}
*path = append(*path, 'L')
if dfs(node.Left, x, path) {
return true
}
(*path)[len(*path)-1] = 'R'
if dfs(node.Right, x, path) {
return true
}
*path = (*path)[:len(*path)-1]
return false
}
node := lca(root, startValue, destValue)
pathToStart := []byte{}
pathToDest := []byte{}
dfs(node, startValue, &pathToStart)
dfs(node, destValue, &pathToDest)
return string(bytes.Repeat([]byte{'U'}, len(pathToStart))) + string(pathToDest)
}Approach 4: Lowest Common Ancestor + DFS (Optimized)
We can start from root, find the paths to startValue and destValue, denoted as pathToStart and pathToDest, respectively. Then, remove the longest common prefix of pathToStart and pathToDest. At this point, the length of pathToStart is the number of Us in the answer, and the path of pathToDest is the path in the answer. We just need to concatenate these two paths.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getDirections(root: TreeNode | null, startValue: number, destValue: number): string {
const dfs = (node: TreeNode | null, x: number, path: string[]): boolean => {
if (node === null) {
return false;
}
if (node.val === x) {
return true;
}
path.push('L');
if (dfs(node.left, x, path)) {
return true;
}
path[path.length - 1] = 'R';
if (dfs(node.right, x, path)) {
return true;
}
path.pop();
return false;
};
const pathToStart: string[] = [];
const pathToDest: string[] = [];
dfs(root, startValue, pathToStart);
dfs(root, destValue, pathToDest);
let i = 0;
while (pathToStart[i] === pathToDest[i]) {
++i;
}
return 'U'.repeat(pathToStart.length - i) + pathToDest.slice(i).join('');
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getDirections(root *TreeNode, startValue int, destValue int) string {
var dfs func(node *TreeNode, x int, path *[]byte) bool
dfs = func(node *TreeNode, x int, path *[]byte) bool {
if node == nil {
return false
}
if node.Val == x {
return true
}
*path = append(*path, 'L')
if dfs(node.Left, x, path) {
return true
}
(*path)[len(*path)-1] = 'R'
if dfs(node.Right, x, path) {
return true
}
*path = (*path)[:len(*path)-1]
return false
}
pathToStart := []byte{}
pathToDest := []byte{}
dfs(root, startValue, &pathToStart)
dfs(root, destValue, &pathToDest)
i := 0
for i < len(pathToStart) && i < len(pathToDest) && pathToStart[i] == pathToDest[i] {
i++
}
return string(bytes.Repeat([]byte{'U'}, len(pathToStart)-i)) + string(pathToDest[i:])
}Complexity comparison
| Approach | Complexity |
|---|---|
| Find Paths to Root and Compute Directions | Time Complexity: O(n), where n is the number of nodes, as each node could be traversed in the worst-case. |
| Using Depth-First Search (DFS) to Build Parent Map | Time Complexity: O(n), traversing all nodes for setup. |
| Lowest Common Ancestor + DFS | – |
| Lowest Common Ancestor + DFS (Optimized) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Find Paths to Root and Compute Directions | O(n) | O(n) | Best general solution. Clean logic using root-to-node paths and LCA comparison. |
| DFS Parent Map + Graph Traversal | O(n) | O(n) | Useful when treating the tree as an undirected graph with parent links. |
Frequently asked questions
Is Step-By-Step Directions From a Binary Tree Node to Another easy or hard?
This problem is classified as Medium difficulty. The challenge comes from recognizing that the path between two nodes goes through their lowest common ancestor and translating that relationship into direction characters.
Step-By-Step Directions From a Binary Tree Node to Another Python/Java solution
Python and Java solutions typically implement DFS to build paths or parent maps. After identifying the lowest common ancestor or exploring neighbors, the algorithm constructs the direction string using 'L', 'R', and 'U'. Both implementations run in O(n) time and use O(n) auxiliary space.
How to solve Step-By-Step Directions From a Binary Tree Node to Another in O(n)?
Run a depth-first search from the root to record paths to both the start node and destination node. Compare the paths to find the first position where they differ, which represents the lowest common ancestor. Convert the remaining start path to 'U' moves and append the remaining destination path moves to build the final direction string.
What is the best approach for Step-By-Step Directions From a Binary Tree Node to Another?
The most common approach finds the path from the root to both nodes using DFS, then identifies the lowest common ancestor by comparing the two paths. Replace the remaining steps in the start path with 'U' and append the remaining moves from the destination path. This runs in O(n) time and O(n) space and is typically expected in coding interviews.
Is Step-By-Step Directions From a Binary Tree Node to Another asked at Google/Amazon/Meta?
Binary tree path and lowest common ancestor style problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test DFS traversal, tree path construction, and reasoning about ancestor relationships.
What data structure is used in Step-By-Step Directions From a Binary Tree Node to Another?
The solution primarily uses binary tree traversal with recursion or an explicit stack. Some implementations also maintain arrays for root-to-node paths or a hash map that stores each node's parent to allow upward traversal in the tree.
What is the time complexity of Step-By-Step Directions From a Binary Tree Node to Another?
The optimal solutions run in O(n) time where n is the number of nodes in the binary tree. Each node is visited at most once during DFS traversal. Space complexity is O(n) due to recursion stack, path storage, or the parent map used during traversal.