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

The problem gives us a binary tree where every node contains a unique value from 1 to n. We are also given two node values: - startValue, the node where the path begins - destValue, the node where the path must end We must return the shortest sequence of directions needed to…

leetcodemediumstringtreedepth-first-searchbinary-tree

LeetCode Problem 2096

Difficulty: 🟡 Medium
Topics: String, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem gives us a binary tree where every node contains a unique value from 1 to n. We are also given two node values:

  • startValue, the node where the path begins
  • destValue, the node where the path must end

We must return the shortest sequence of directions needed to move from the start node to the destination node.

The output string may contain only three characters:

  • 'L' means move from a node to its left child
  • 'R' means move from a node to its right child
  • 'U' means move from a node to its parent

Because the structure is a tree, there is exactly one unique path between any two nodes. That means the shortest path is also uniquely determined.

The main challenge is converting the relationship between two nodes into a direction string. A direct traversal from one node to another is difficult because tree nodes do not contain parent pointers. However, binary trees naturally support root-to-node traversal, and that observation leads to the optimal solution.

The constraints are important:

  • The tree can contain up to 10^5 nodes
  • Node values are unique
  • Both target nodes are guaranteed to exist
  • startValue != destValue

Since the tree can be very large, any algorithm worse than linear time risks timing out. Repeated traversals or rebuilding paths many times would be inefficient. We need an approach that processes the tree efficiently in one pass or a small constant number of passes.

Several edge cases are important:

  • One node may be an ancestor of the other
  • The root may be either the start or destination
  • The path may require only upward moves
  • The path may require only downward moves
  • The lowest common ancestor may be deep in the tree

A correct implementation must handle all of these situations consistently.

Approaches

Brute Force Approach

A brute force solution would first convert the tree into an undirected graph. Every node would connect to:

  • its left child
  • its right child
  • its parent

After building this graph, we could run Breadth-First Search from startValue until we reach destValue.

While exploring neighbors, we would store both:

  • the previous node
  • the direction used to reach the next node

Once the destination is found, we could reconstruct the shortest path by backtracking through the BFS parent map.

This works because BFS guarantees the shortest path in an unweighted graph.

However, this approach has drawbacks:

  • We must first traverse the entire tree to build parent relationships
  • We need additional graph structures
  • BFS stores extra state for every node
  • The implementation is more complicated than necessary

Although the asymptotic complexity is still linear, the extra memory overhead and graph conversion are unnecessary because trees already have a strong hierarchical structure we can exploit directly.

Optimal Approach

The key observation is that the shortest path between two tree nodes always passes through their Lowest Common Ancestor, often abbreviated as LCA.

Instead of navigating directly between nodes, we can:

  1. Find the path from the root to startValue
  2. Find the path from the root to destValue
  3. Remove the common prefix from both paths

The shared prefix represents the path from the root to the LCA.

After removing the common prefix:

  • Every remaining step in the start path must become 'U'
  • The remaining destination path already contains the correct 'L' and 'R' directions

This transforms the problem into a clean path comparison problem.

For example:

  • Root to start: "LLR"
  • Root to destination: "LRR"

Common prefix: "L"

Remaining:

  • start suffix: "LR"
  • destination suffix: "RR"

To move from start to destination:

  • go up twice: "UU"
  • then follow destination suffix: "RR"

Result: "UURR"

This approach is elegant because tree paths naturally encode ancestor relationships.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Build graph and run BFS between nodes
Optimal O(n) O(n) Find root-to-node paths and remove common prefix

Algorithm Walkthrough

  1. Perform a Depth-First Search from the root to find the path to startValue.

While traversing:

  • append 'L' when moving left
  • append 'R' when moving right

If the target is found, stop recursion and keep the constructed path. 2. Perform another Depth-First Search to find the path from the root to destValue.

This produces another sequence of 'L' and 'R' directions. 3. Compare both paths character by character from the beginning.

The matching prefix corresponds to the shared route from the root down to the Lowest Common Ancestor. 4. Stop when the paths diverge.

At that point:

  • the remaining portion of the start path represents how far below the LCA the start node is
  • the remaining portion of the destination path represents how to reach the destination from the LCA
  1. Replace every remaining direction in the start path with 'U'.

Each leftover step means we must move upward toward the LCA. 6. Append the remaining destination suffix.

These directions already describe the correct downward traversal from the LCA to the destination. 7. Return the final combined string.

Why it works

Every path in a tree is unique. The root-to-start path and root-to-destination path share an identical prefix up to the Lowest Common Ancestor. Once the paths diverge, the only way to move from the start node to the destination is:

  • move upward from the start node to the LCA
  • then move downward from the LCA to the destination

Replacing the remaining start suffix with 'U' operations and appending the remaining destination suffix exactly reconstructs this unique shortest path.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def getDirections(
        self,
        root: Optional[TreeNode],
        startValue: int,
        destValue: int
    ) -> str:

        def find_path(node: Optional[TreeNode], target: int, path: list[str]) -> bool:
            if not node:
                return False

            if node.val == target:
                return True

            path.append("L")
            if find_path(node.left, target, path):
                return True
            path.pop()

            path.append("R")
            if find_path(node.right, target, path):
                return True
            path.pop()

            return False

        start_path = []
        dest_path = []

        find_path(root, startValue, start_path)
        find_path(root, destValue, dest_path)

        common_length = 0

        while (
            common_length < len(start_path)
            and common_length < len(dest_path)
            and start_path[common_length] == dest_path[common_length]
        ):
            common_length += 1

        up_moves = "U" * (len(start_path) - common_length)
        down_moves = "".join(dest_path[common_length:])

        return up_moves + down_moves

The implementation begins with a helper DFS function named find_path. This function searches for a target node while simultaneously building the path from the root.

The path list acts like a recursion stack. Before moving left, the algorithm appends 'L'. Before moving right, it appends 'R'. If a branch does not contain the target, the last direction is removed using pop(). This is classic backtracking.

Once the target node is found, the function immediately returns True, preserving the successful path.

After collecting both root-to-node paths, the algorithm computes the length of their common prefix. This identifies the Lowest Common Ancestor implicitly.

The remaining directions in start_path become upward moves, represented by 'U'.

The remaining suffix of dest_path is already the correct downward route from the LCA to the destination.

Finally, both pieces are concatenated and returned.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getDirections(root *TreeNode, startValue int, destValue int) string {

	var findPath func(node *TreeNode, target int, path *[]byte) bool

	findPath = func(node *TreeNode, target int, path *[]byte) bool {
		if node == nil {
			return false
		}

		if node.Val == target {
			return true
		}

		*path = append(*path, 'L')
		if findPath(node.Left, target, path) {
			return true
		}
		*path = (*path)[:len(*path)-1]

		*path = append(*path, 'R')
		if findPath(node.Right, target, path) {
			return true
		}
		*path = (*path)[:len(*path)-1]

		return false
	}

	startPath := []byte{}
	destPath := []byte{}

	findPath(root, startValue, &startPath)
	findPath(root, destValue, &destPath)

	commonLength := 0

	for commonLength < len(startPath) &&
		commonLength < len(destPath) &&
		startPath[commonLength] == destPath[commonLength] {

		commonLength++
	}

	result := make([]byte, 0)

	for i := commonLength; i < len(startPath); i++ {
		result = append(result, 'U')
	}

	result = append(result, destPath[commonLength:]...)

	return string(result)
}

The Go implementation follows the same algorithmic structure as the Python version, but there are several language-specific details.

Go does not have mutable strings, so paths are stored as []byte slices. This allows efficient append and backtracking operations.

The helper DFS receives a pointer to the slice so recursive calls can modify the shared path directly.

Backtracking is implemented by shrinking the slice using:

*path = (*path)[:len(*path)-1]

The final result is built incrementally using another byte slice and converted to a string at the end.

Because the maximum path length is at most n, there is no integer overflow concern in this problem.

Worked Examples

Example 1

Input:

root = [5,1,2,3,null,6,4]
startValue = 3
destValue = 6

Tree structure:

        5
       / \
      1   2
     /   / \
    3   6   4

Step 1: Find path to start node

Path from root to 3:

Current Node Move Path
5 L L
1 L LL
3 found LL

Result:

start_path = "LL"

Step 2: Find path to destination node

Path from root to 6:

Current Node Move Path
5 R R
2 L RL
6 found RL

Result:

dest_path = "RL"

Step 3: Remove common prefix

Compare:

LL
RL

No common prefix exists.

So:

common_length = 0

Step 4: Build final answer

Remaining start suffix:

LL

This becomes:

UU

Remaining destination suffix:

RL

Final result:

"UURL"

This corresponds to:

3 -> 1 -> 5 -> 2 -> 6

Example 2

Input:

root = [2,1]
startValue = 2
destValue = 1

Tree structure:

    2
   /
  1

Step 1: Find paths

Root to 2:

""

Root to 1:

"L"

Step 2: Remove common prefix

The start path is empty, so the common prefix length is 0.

Step 3: Construct result

Upward moves:

""

Destination suffix:

"L"

Final answer:

"L"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each DFS traversal may visit every node once
Space O(n) Recursive call stack and stored paths may grow to tree height

The algorithm performs two DFS traversals, one for each target node. In the worst case, each traversal visits every node exactly once, resulting in linear time complexity.

The space complexity comes from recursion depth and stored path arrays. In a highly unbalanced tree, the recursion stack may reach O(n) depth. The stored paths can also contain up to O(n) directions.

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(
    5,
    TreeNode(1, TreeNode(3)),
    TreeNode(2, TreeNode(6), TreeNode(4))
)
assert solution.getDirections(root1, 3, 6) == "UURL"  # mixed upward and downward movement

# Example 2
root2 = TreeNode(2, TreeNode(1))
assert solution.getDirections(root2, 2, 1) == "L"  # direct left child

# Destination is ancestor of start
root3 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(3)
    )
)
assert solution.getDirections(root3, 3, 1) == "UU"  # only upward movement

# Start is ancestor of destination
root4 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(3)
    )
)
assert solution.getDirections(root4, 1, 3) == "LL"  # only downward movement

# Lowest common ancestor is root
root5 = TreeNode(
    1,
    TreeNode(2),
    TreeNode(3)
)
assert solution.getDirections(root5, 2, 3) == "UR"  # move up then right

# Deep unbalanced tree
root6 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(
            3,
            TreeNode(4)
        )
    )
)
assert solution.getDirections(root6, 4, 2) == "UU"  # deep upward traversal

# Right-heavy tree
root7 = TreeNode(
    1,
    None,
    TreeNode(
        2,
        None,
        TreeNode(3)
    )
)
assert solution.getDirections(root7, 1, 3) == "RR"  # repeated right traversal

# Complex branching
root8 = TreeNode(
    10,
    TreeNode(
        5,
        TreeNode(3),
        TreeNode(7)
    ),
    TreeNode(
        15,
        TreeNode(12),
        TreeNode(18)
    )
)
assert solution.getDirections(root8, 3, 18) == "UURR"  # across subtrees
Test Why
Example 1 Validates mixed upward and downward traversal
Example 2 Validates direct parent-child movement
Destination is ancestor Ensures multiple 'U' moves work correctly
Start is ancestor Ensures pure downward traversal works
LCA is root Validates crossing between subtrees
Deep unbalanced tree Tests recursion depth behavior
Right-heavy tree Ensures repeated right traversal works
Complex branching Tests longer paths through the root

Edge Cases

One important edge case occurs when the destination node is an ancestor of the start node. In this situation, the correct answer contains only 'U' characters. A buggy implementation might incorrectly attempt additional downward moves after reaching the ancestor. This solution handles the case naturally because the destination suffix becomes empty after removing the common prefix.

Another critical case occurs when the start node is an ancestor of the destination node. Here, no upward movement is required. The algorithm correctly produces only the remaining destination suffix because the start suffix after the common prefix has length zero.

A highly unbalanced tree is also important to consider. If the tree resembles a linked list, recursive DFS depth can become O(n). The algorithm still remains correct because each node is visited only once per traversal, though recursion depth becomes large. This matches the theoretical worst-case space complexity.

A final subtle case occurs when the Lowest Common Ancestor is the root itself. In that scenario, the root-to-node paths diverge immediately, so the common prefix length is zero. The algorithm correctly converts the entire start path into upward moves and appends the entire destination path afterward.