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

Problem

Find the string of step directions ('L', 'R', 'U') to go from node startValue to node destValue.

Key insight: Find LCA. Path = go up from start to LCA (all 'U'), then go down from LCA to dest.

Approach

Find path from root to start: path_s
Find path from root to dest: path_d
Strip common prefix (= path through LCA)
Result = 'U' * len(remaining path_s) + remaining path_d

Solutions

// C++
bool findPath(TreeNode* node, int target, string& path) {
    if (!node) return false;
    if (node->val == target) return true;
    path += 'L';
    if (findPath(node->left, target, path)) return true;
    path.pop_back();
    path += 'R';
    if (findPath(node->right, target, path)) return true;
    path.pop_back();
    return false;
}
string getDirections(TreeNode* root, int startValue, int destValue) {
    string ps, pd;
    findPath(root, startValue, ps);
    findPath(root, destValue, pd);
    int i = 0;
    while (i < ps.size() && i < pd.size() && ps[i] == pd[i]) i++;
    return string(ps.size() - i, 'U') + pd.substr(i);
}

// Java
boolean findPath(TreeNode node, int target, StringBuilder path) {
    if (node == null) return false;
    if (node.val == target) return true;
    path.append('L');
    if (findPath(node.left, target, path)) return true;
    path.deleteCharAt(path.length()-1);
    path.append('R');
    if (findPath(node.right, target, path)) return true;
    path.deleteCharAt(path.length()-1);
    return false;
}
public String getDirections(TreeNode root, int startValue, int destValue) {
    StringBuilder ps = new StringBuilder(), pd = new StringBuilder();
    findPath(root, startValue, ps);
    findPath(root, destValue, pd);
    String s = ps.toString(), d = pd.toString();
    int i = 0;
    while (i < s.length() && i < d.length() && s.charAt(i) == d.charAt(i)) i++;
    return "U".repeat(s.length() - i) + d.substring(i);
}

// JavaScript
function getDirections(root, startValue, destValue) {
    function findPath(node, target, path) {
        if (!node) return false;
        if (node.val === target) return true;
        path.push('L');
        if (findPath(node.left, target, path)) return true;
        path.pop();
        path.push('R');
        if (findPath(node.right, target, path)) return true;
        path.pop();
        return false;
    }
    const ps = [], pd = [];
    findPath(root, startValue, ps);
    findPath(root, destValue, pd);
    let i = 0;
    while (i < ps.length && i < pd.length && ps[i] === pd[i]) i++;
    return 'U'.repeat(ps.length - i) + pd.slice(i).join('');
}

# Python
def getDirections(root, startValue, destValue):
    def find_path(node, target, path):
        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

    ps, pd = [], []
    find_path(root, startValue, ps)
    find_path(root, destValue, pd)
    i = 0
    while i < len(ps) and i < len(pd) and ps[i] == pd[i]:
        i += 1
    return 'U' * (len(ps) - i) + ''.join(pd[i:])

Complexity

Time: O(n)
Space: O(n)

Key Insight

Common prefix of root-to-start and root-to-dest paths = path through LCA. Strip it, replace start's portion with 'U's.