Step-by-Step Directions via LCA

Paths Between Two Nodes

Every tree path problem eventually reduces to the same core idea: find the LCA, then stitch together the two half-paths. This problem makes that completely explicit by asking you to output the actual directions.

Problem: Step-By-Step Directions (LC 2096)

Problem: You are given the root of a binary tree with $n$ nodes, each with a unique value. You are also given a $startValue$ and a $destValue$. Find the shortest path from the node with $startValue$ to the node with $destValue$ and return it as a string of directions:

'U' — move to parent
'L' — move to left child
'R' — move to right child

$startValue = 3$, $destValue = 6$. Answer: "UURL".

The path: $3 \xrightarrow{U} 1 \xrightarrow{U} 5 \xrightarrow{R} 2 \xrightarrow{L} 6$.

The Key Observation

Any path between two nodes in a tree goes up from the source to their Lowest Common Ancestor (LCA), then down from the LCA to the destination. There are no shortcuts — trees have exactly one path between any two nodes.

So the problem breaks into three pieces:

Find the path from root to source (a string of L's and R's).
Find the path from root to destination (a string of L's and R's).
Strip the common prefix (the shared path from root to LCA), convert the remaining source path to all U's, and append the remaining destination path.

The approach: Find both root-to-node paths, strip their common prefix (that's the LCA), then the answer is U's for the source remainder + L/R's for the destination remainder.

Two paths from root to source and destination, with common prefix stripped to reveal the LCA

Why This Works

Consider the paths from root to each node:

Root to source (node 3): L, L ($5 \to 1 \to 3$)
Root to dest (node 6): R, L ($5 \to 2 \to 6$)

Common prefix: empty (they diverge immediately — 'L' vs 'R'). The LCA is the root (node 5).

Source remainder: "LL" — that's 2 steps up, so "UU".
Dest remainder: "RL" — that's the downward path.
Result: "UU" + "RL" = "UURL".

Now consider $startValue = 3$, $destValue = 1$ on the same tree:

Root to source (node 3): L, L
Root to dest (node 1): L

Common prefix: "L" (the path to node 1). The LCA is node 1.

Source remainder after stripping "L": "L" — that's 1 step up, so "U".
Dest remainder after stripping "L": "" — already at destination.
Result: "U".

Full Trace

$startValue = 3$, $destValue = 6$.

Step 1: Find path from root to node 3.

Node visited	Direction taken	Path so far
5	L (go to child 1)	"L"
1	L (go to child 3)	"LL"
3	found target	"LL"

$pathToSource = $ "LL"

Step 2: Find path from root to node 6.

Node visited	Direction taken	Path so far
5	R (go to child 2)	"R"
2	L (go to child 6)	"RL"
6	found target	"RL"

$pathToDest = $ "RL"

Step 3: Strip common prefix and build result.

Index	pathToSource[i]	pathToDest[i]	Match?
0	L	R	No — stop

Common prefix length: 0. LCA is the root (node 5).

Source remainder: "LL" (length 2) $\to$ "UU"
Dest remainder: "RL"
Final answer: "UU" + "RL" = "UURL"

Manual verification: $3 \xrightarrow{U} 1 \xrightarrow{U} 5 \xrightarrow{R} 2 \xrightarrow{L} 6$. Correct.

The Code

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.pop_back();

    path.push_back('R');
    if (findPath(node->right, target, path)) return true;
    path.pop_back();

    return false;
}

string getDirections(TreeNode* root, int startValue, int destValue) {
    string pathToSource, pathToDest;
    findPath(root, startValue, pathToSource);
    findPath(root, destValue, pathToDest);

    int commonLength = 0;
    while (commonLength < (int)pathToSource.size()
           && commonLength < (int)pathToDest.size()
           && pathToSource[commonLength] == pathToDest[commonLength]) {
        commonLength++;
    }

    string result(pathToSource.size() - commonLength, 'U');
    result += pathToDest.substr(commonLength);
    return result;
}

Complexity: $O(n)$ time (two DFS passes + one linear scan of paths), $O(n)$ space.

Why Not Find LCA Explicitly?

You could find the LCA first, then build paths from LCA to source and LCA to dest. But finding root-to-node paths and stripping the common prefix implicitly finds the LCA without a separate function. The common prefix IS the path from root to LCA.

Both approaches are $O(n)$. The path-stripping version is cleaner to implement and avoids writing a separate LCA function. On an OA, fewer moving parts means fewer bugs.

Try It

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"

Predict before running: What if source and dest are the same node? Both paths are identical, common prefix covers everything, source remainder is empty, dest remainder is empty. Result: "". That's correct — you're already there.

Challenge: What if the tree is a straight line (every node has only a left child) with $10^5$ nodes, and source is the deepest node while dest is the root? The path string will be $10^5$ U's. Does the solution still run in $O(n)$?

Problems

Problem	Link	Difficulty
LC 2096 --- Step-By-Step Directions	leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another	Medium
LC 236 --- Lowest Common Ancestor	leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree	Medium
LC 257 --- Binary Tree Paths	leetcode.com/problems/binary-tree-paths	Easy
LC 129 — Sum Root to Leaf Numbers	leetcode.com/problems/sum-root-to-leaf-numbers	Medium
LC 1443 — Min Time to Collect Apples	leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree	Medium
LC 1376 — Time to Inform All Employees	leetcode.com/problems/time-needed-to-inform-all-employees	Medium

What's Next?

You can now traverse trees in every direction and solve view/path/distance problems. But what about building trees from scratch? Chapter 5 teaches construction — from traversal pairs, serialization, and flattening.