⚡Flashcard Drill➔
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

  1. Find the path from the root to each of the two nodes as strings of 'L'/'R'.
  2. The common prefix of those two paths is the path to the lowest common ancestor.
  3. To go from the start node to the LCA, replace the remaining suffix of the start path with 'U'.
  4. 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 the or would continue searching. Returning None for "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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems