NeetCode #467LC-2096MediumTrees
← Back to All Problems#467 · #2096 · Step-By-Step Directions From a Binary Tree Node to Another(从二叉树一个节点到另一个节点每一步的方向)
📌 Problem Statement & Constraints
Given the root of a binary tree with unique values from 1 to n, and two values
startValue and endValue, return the shortest path from the start node to the end node as a string of 'L', 'R' and 'U'. Constraints: the number of nodes is in [2, 10^5], all values are distinct.💡 Core Algorithmic Approaches
- Find the path from the root to each of the two nodes as strings of
'L'/'R'. - The common prefix of those two paths is the path to the lowest common ancestor.
- To go from the start node to the LCA, replace the remaining suffix of the start path with
'U'. - Then append the remaining suffix of the end path. The result is the shortest path, since it is the unique simple path in a tree.
💻 Benchmark Python3 Implementation
class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int, endValue: int) -> str:
def find(node: Optional[TreeNode], target: int, path: str) -> Optional[str]:
if not node:
return None
if node.val == target:
return path
return (find(node.left, target, path + "L")
or find(node.right, target, path + "R"))
ps = find(root, startValue, "")
pe = find(root, endValue, "")
# strip the common prefix (the path to the LCA)
i = 0
while i < len(ps) and i < len(pe) and ps[i] == pe[i]:
i += 1
# go up to the LCA, then follow the end path down
return "U" * (len(ps) - i) + pe[i:]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) for the two searches, plus O(path length) for the assembly.
💾 Space Complexity
O(h) for the recursion plus the path strings.
⚠️ Interview Pitfalls & Follow-ups
- Trying to walk the tree directly from start to end: a node has no parent pointer, so the upward moves cannot be executed.
- Not stripping the common prefix: the path would revisit the shared ancestors instead of going straight up to the LCA.
- Using
find(...) or find(...)with an empty string as the base path: an empty path is falsy, so theorwould continue searching. ReturningNonefor "not found" and a string (possibly"") for "found" avoids this -- and since the root's path is"", the caller must handle it. A safer formulation returns a tuple(found, path). - Assuming the tree is a BST: it is a general binary tree, so both subtrees must be searched.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.