MediumStringTreeDepth-First SearchBinary TreeBinary LiftingLowest Common AncestorUpdated Sep 2026

2096. Step-By-Step Directions From a Binary Tree Node to Another

Asked at Databricks, Snowflake

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

String

Companies

2

Problem

You get the root of a binary tree where every node holds a unique value. You also get two values: startValue and destValue. They point to two different nodes in the tree.

Your job is to return the shortest path from the start node to the destination node, written as a string of directions. Use only three letters: 'L' means move to the left child, 'R' means move to the right child, and 'U' means move up to the parent.

The path must be the shortest one. In a tree there is exactly one simple path between two nodes, so the answer is unique. Note that you cannot jump straight from one branch to another — you must walk up to the point where the two branches meet, then walk down.

Walk up, then walk down

3start = 315meeting point6dest = 6243 → 1 → 5 → 2 → 6, written as UURL
The route from 3 to 6 must climb to node 5, the meeting point of both branches, then descend to 6.

Constraints

  • ●2 <= n <= 10^5, where n is the number of nodes
  • ●1 <= Node.val <= n
  • ●All node values are unique
  • ●1 <= startValue, destValue <= n
  • ●startValue != destValue

Examples

Example 1
Inputroot = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
OutputUURL
WhyNode 3 is the left child of 1. Node 6 is the left child of 2. The only route is 3 → 1 → 5 → 2 → 6. Going up twice gives "UU", then right to 2 gives "R", then left to 6 gives "L".
Example 2
Inputroot = [2,1], startValue = 2, destValue = 1
OutputL
WhyNode 1 is the left child of node 2, so one move to the left is enough.

Asked At

2 companies
CompanyDifficulty
DatabricksMediumView all Databricks questions →
SnowflakeMediumView all Snowflake questions →

How to Think About It

1

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.

2

Improved: Use DFS to find the path from root to each target node, storing the sequence of directions.

3

Better: Find LCA of both nodes. From start, generate U moves to reach LCA. From LCA, generate L/R moves to reach dest.

4

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.

5

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.

Compare the two root paths

path to 3LL01From the root, 3 is reached by left, leftpath to 6RL01From the root, 6 is reached by right, leftshared prefix = "" (length 0)U moves = 2 → "UU"dest moves = "RL"answer = "UU" + "RL" = "UURL"
The shared prefix points to the meeting node. The leftover start part becomes U moves, and the leftover dest part is copied as-is.
ComplexityTime O(n)Space O(n)Each node is visited once during DFS, and the two direction paths can each be as long as the tree height.

Solution Code

O(n) time
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 + destMoves

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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, Snowflake. It is a medium difficulty problem.