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

Step-By-Step Directions From a Binary Tree Node to Another - Problem

You are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.

Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:

'L' means to go from a node to its left child node.
'R' means to go from a node to its right child node.
'U' means to go from a node to its parent node.

Return the step-by-step directions of the shortest path from node s to node t.

Input & Output

Example 1 — Basic Tree Navigation

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

› Output: UUUL

💡 Note: Start at node 3, go up twice to reach node 5 (root), then down left to node 1, then down right to reach node 6. Path: 3→1→5→1→6 gives directions UUUL.

Example 2 — Sibling Nodes

$ Input: root = [2,1,3], startValue = 3, destValue = 1

› Output: UL

💡 Note: Start at node 3 (right child), go up to root node 2, then left to node 1. Simple sibling traversal: 3→2→1 gives UL.

Example 3 — Same Subtree

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

› Output: UURR

💡 Note: From node 3 to node 4: go up to node 1, then up to root 5, then right to node 2, then right to node 4. Path gives UURR.

Constraints

The number of nodes in the tree is n.
2 ≤ n ≤ 10⁵
1 ≤ Node.val ≤ n
All values in the tree are unique.
startValue ≠ destValue

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with unique node values and two target nodes

Find Paths

Use DFS to locate paths from root to both start and destination nodes

Build Directions

Create string of L/R/U moves representing the shortest path

Key Takeaway

🎯 Key Insight: The shortest path always goes through the lowest common ancestor of the two nodes

Asked in

f Facebook 25 a Amazon 18 G Google 15 M Microsoft 12

The key insight is to find paths from root to both nodes, then identify their lowest common ancestor by finding the common prefix. The optimal approach uses DFS to find these paths and removes the common portion to create the shortest path. Best approach is DFS with LCA optimization: Time O(n), Space O(h).

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Lowest Common Ancestor	O(n)	O(h)	Find LCA first, then build optimal path through the common ancestor
Brute Force - Full Path Recording	O(n)	O(h)	Find complete paths from root to both nodes, then combine them

DFS with Lowest Common Ancestor — Algorithm Steps

Step 1: Find lowest common ancestor (LCA) of start and dest nodes
Step 2: Find path from LCA to start node
Step 3: Find path from LCA to dest node
Step 4: Reverse start path to 'U's and append dest path

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Paths

Get paths from root to both start and destination

Find LCA

Identify common prefix in both paths

Optimize

Remove common prefix and build shortest path

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

bool findPath(struct TreeNode* node, int target, char* path, int* pathLen) {
    if (!node) return false;
    if (node->val == target) return true;
    
    path[(*pathLen)++] = 'L';
    if (findPath(node->left, target, path, pathLen)) return true;
    (*pathLen)--;
    
    path[(*pathLen)++] = 'R';
    if (findPath(node->right, target, path, pathLen)) return true;
    (*pathLen)--;
    
    return false;
}

char* solution(struct TreeNode* root, int startValue, int destValue) {
    char startPath[1000], destPath[1000];
    int startLen = 0, destLen = 0;
    
    findPath(root, startValue, startPath, &startLen);
    findPath(root, destValue, destPath, &destLen);
    
    // Find common prefix
    int i = 0;
    while (i < startLen && i < destLen && startPath[i] == destPath[i]) {
        i++;
    }
    
    char* result = (char*)malloc((startLen - i + destLen - i + 1) * sizeof(char));
    int idx = 0;
    
    // Add up moves
    for (int j = i; j < startLen; j++) {
        result[idx++] = 'U';
    }
    // Add down moves
    for (int j = i; j < destLen; j++) {
        result[idx++] = destPath[j];
    }
    result[idx] = '\0';
    
    return result;
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // Simplified tree building for basic test case
    struct TreeNode* root = createNode(5);
    root->left = createNode(1);
    root->right = createNode(2);
    root->left->left = createNode(3);
    root->right->left = createNode(6);
    root->right->right = createNode(4);
    
    int startValue, destValue;
    char line[1000];
    fgets(line, sizeof(line), stdin); // Skip tree input for simplicity
    scanf("%d", &startValue);
    scanf("%d", &destValue);
    
    char* result = solution(root, startValue, destValue);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single DFS traversal to find paths, each node visited at most twice

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h for DFS traversal

✓ Linear Space

89.5K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Lowest Common Ancestor — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler