Step-By-Step Directions From a Binary Tree Node to Another
Asked at Databricks
Problem
Given the root of a binary tree with unique values and two node values startValue and destValue, construct a string of directions (L, R, U) representing the shortest path from the start node to the destination node. The path must use only L for left child, R for right child, and U for parent.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
How to Think About It
Brute force: Find paths from root to both nodes, then trace from start to LCA via U moves and from LCA to dest via L/R moves.
Improved: Use DFS to find the path from root to each target node, storing the sequence of directions.
Better: Find LCA of both nodes. From start, generate U moves to reach LCA. From LCA, generate L/R moves to reach dest.
Refined: DFS to find path to each node as a list of directions. The shared prefix up to LCA is trimmed, remaining start path becomes U moves.
Optimal: Single DFS that builds paths to both start and dest simultaneously. Find LCA by comparing paths. Output U repeated (pathLen - LCA depth) plus remaining path to dest. O(n) time, O(n) space.
Optimal Approach
Use DFS to find the path from root to both startValue and destValue as sequences of directions. The Lowest Common Ancestor (LCA) is the node where the two paths diverge. From startValue, we need to go up to the LCA, which means appending U for each step remaining in the start path after the LCA. From the LCA, we follow the path to destValue using L and R directions. Combine the U-prefix with the LCA-to-dest suffix to form the final directions string. This runs in O(n) time for DFS traversal and O(n) space for path storage.
Solution Code
def getDirections(root, startValue, destValue):
def findPath(node, target, path):
if not node:
return False
if node.val == target:
return True
path.append('L')
if findPath(node.left, target, path):
return True
path.pop()
path.append('R')
if findPath(node.right, target, path):
return True
path.pop()
return False
startPath = []
destPath = []
findPath(root, startValue, startPath)
findPath(root, destValue, destPath)
i = 0
while i < len(startPath) and i < len(destPath) and startPath[i] == destPath[i]:
i += 1
uMoves = 'U' * (len(startPath) - i)
destMoves = ''.join(destPath[i:])
return uMoves + destMovesFrequently Asked Questions
What is the Step-By-Step Directions From a Binary Tree Node to Another problem?
Given the root of a binary tree with unique values and two node values startValue and destValue, construct a string of directions (L, R, U) representing the shortest path from the start node to the destination node. The path must use only L for left child, R for right child, and U for parent.
How do you solve Step-By-Step Directions From a Binary Tree Node to Another?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Step-By-Step Directions From a Binary Tree Node to Another?
Step-By-Step Directions From a Binary Tree Node to Another is asked at Databricks. It is a medium difficulty problem.