2096. 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.

  Example 1:

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.

Example 2:

Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation: The shortest path is: 2 → 1.

  Constraints:

• The number of nodes in the tree is n.

• 2 <= n <= 105

• 1 <= Node.val <= n

• All the values in the tree are unique.

• 1 <= startValue, destValue <= n

• startValue != destValue

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} startValue
 * @param {number} destValue
 * @return {string}
 */
var getDirections = function(root, startValue, destValue) {
    var findLCA = function(node) {
        if (!node) return false;
        if (node.val === startValue || node.val === destValue) {
            return node;
        }
        var left = findLCA(node.left);
        var right = findLCA(node.right);
        return (left && right) ? node : (left || right || false);
    };
    var findStart = function(node) {
        if (!node) return null;
        if (node.val === startValue) return '';

        var left = findStart(node.left);
        if (left !== null) return left + 'U';

        var right = findStart(node.right);
        if (right !== null) return right + 'U';

        return null;
    };
    var findDest = function(node) {
        if (!node) return null;
        if (node.val === destValue) return '';

        var left = findDest(node.left);
        if (left !== null) return 'L' + left;

        var right = findDest(node.right);
        if (right !== null) return 'R' + right;

        return null;
    };
    var LCA = findLCA(root);
    var startPath = findStart(LCA);
    var destPath = findDest(LCA);
    return startPath + destPath;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).