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

medium binary tree lca paths

Problem

You are given a binary tree whose n nodes hold distinct values 1..n, plus two of those values: startValue and destValue. Standing on the start node, you may move 'U' (up to the parent), 'L' (down to the left child), or 'R' (down to the right child).

Return the shortest sequence of such moves, as a string, that walks from the start node to the destination node.

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

Output"UURL"

From 3 climb up twice to the root 5 (their lowest common ancestor), then go right to 2 and left to 6.

tree (level-order, "null" for a missing child)

startValue

destValue

def get_directions(root, start_value, dest_value):
    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[-1] = "R"
        if find_path(node.right, target, path):
            return True
        path.pop()
        return False

    p_start, p_dest = [], []
    find_path(root, start_value, p_start)
    find_path(root, dest_value, p_dest)
    i = 0
    while i < len(p_start) and i < len(p_dest) and p_start[i] == p_dest[i]:
        i += 1
    return "U" * (len(p_start) - i) + "".join(p_dest[i:])

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[path.length - 1] = "R";
    if (findPath(node.right, target, path)) return true;
    path.pop();
    return false;
  }
  const pStart = [], pDest = [];
  findPath(root, startValue, pStart);
  findPath(root, destValue, pDest);
  let i = 0;
  while (i < pStart.length && i < pDest.length && pStart[i] === pDest[i]) i++;
  return "U".repeat(pStart.length - i) + pDest.slice(i).join("");
}

String getDirections(TreeNode root, int startValue, int destValue) {
    StringBuilder pStart = new StringBuilder(), pDest = new StringBuilder();
    findPath(root, startValue, pStart);
    findPath(root, destValue, pDest);
    int i = 0;
    while (i < pStart.length() && i < pDest.length()
            && pStart.charAt(i) == pDest.charAt(i)) i++;
    StringBuilder ans = new StringBuilder();
    for (int k = i; k < pStart.length(); k++) ans.append('U');
    ans.append(pDest, i, pDest.length());
    return ans.toString();
}

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.setCharAt(path.length() - 1, 'R');
    if (findPath(node.right, target, path)) return true;
    path.deleteCharAt(path.length() - 1);
    return false;
}

class Solution {
public:
    string getDirections(TreeNode* root, int startValue, int destValue) {
        string pStart, pDest;
        findPath(root, startValue, pStart);
        findPath(root, destValue, pDest);
        int i = 0;
        while (i < (int)pStart.size() && i < (int)pDest.size()
                && pStart[i] == pDest[i]) i++;
        string ans(pStart.size() - i, 'U');
        ans += pDest.substr(i);
        return ans;
    }

    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.back() = 'R';
        if (findPath(node->right, target, path)) return true;
        path.pop_back();
        return false;
    }
};

Explanation

The shortest walk between two nodes in a tree is forced: climb from the start node up to their lowest common ancestor (LCA), then descend to the destination. Every 'U' move is a climb toward the LCA and every 'L'/'R' move is a step of the downward path, so we never need to search for the answer — we just need both root-to-node paths.

The helper findPath is a DFS with backtracking. It appends "L", tries the left subtree, rewrites the slot to "R" for the right subtree, and pops the character if neither side contains the target. When it returns true, path spells exactly how to walk from the root to that node.

Both paths start at the root, so their longest common prefix is precisely the path from the root down to the LCA. We scan an index i forward while the characters match; everything before i is shared and can be thrown away.

What remains of the start path (len(pStart) - i characters) is the number of edges between the start node and the LCA — each one becomes a 'U'. What remains of the destination path, pDest[i:], is appended unchanged.

Default example: root = [5,1,2,3,null,6,4], start 3, dest 6. The root path to 3 is "LL" and to 6 is "RL". They diverge immediately (i = 0, LCA is the root 5), so the answer is "UU" + "RL" = "UURL".

Each DFS visits every node at most once and the prefix scan is linear in the path lengths, so the total time is O(n); the recursion stack and the two path strings use O(n) space (up to O(h) ≈ O(n) for a skewed tree).

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