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.

&nbsp;
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.


&nbsp;
Constraints:


	The number of nodes in the tree is n.
	2 &lt;= n &lt;= 105
	1 &lt;= Node.val &lt;= n
	All the values in the tree are unique.
	1 &lt;= startValue, destValue &lt;= n
	startValue != destValue


class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        def find(n: TreeNode, val: int, path: List[str]) -> bool:
            if n.val == val:
                return True
            if n.left and find(n.left, val, path):
                path += "L"
            elif n.right and find(n.right, val, path):
                path += "R"
            return path
        s, d = [], []
        find(root, startValue, s)
        find(root, destValue, d)
        while len(s) and len(d) and s[-1] == d[-1]:
            s.pop()
            d.pop()
        return "".join("U" * len(s)) + "".join(reversed(d))
class Solution {
    
    private boolean DFS(TreeNode currNode, StringBuilder path, int destVal) {
        if(currNode == null) return false;
        if(currNode.val == destVal) return true;
        if(DFS(currNode.left, path, destVal)) path.append("L");
        else if(DFS(currNode.right, path, destVal)) path.append("R");
        return path.length() > 0;
    }
    
    public String getDirections(TreeNode root, int startValue, int destValue) {
        StringBuilder startToRoot = new StringBuilder();
        StringBuilder endToRoot = new StringBuilder();
        
        DFS(root, startToRoot, startValue);
        DFS(root, endToRoot, destValue);
        
        int i = startToRoot.length(), j = endToRoot.length();
        int cnt = 0;
        while(i > 0 && j > 0 && startToRoot.charAt(i-1) == endToRoot.charAt(j-1)) {
            cnt++; i--; j--;
        }
        
        String sPath = "U".repeat(startToRoot.length() - cnt);
        String ePath = endToRoot.reverse().toString().substring(cnt, endToRoot.length());
        
        return sPath + ePath;
    }
}
class Solution {
public:
    bool search(TreeNode* root, int target, string &s){
        if(root==NULL) {
            return false;
        }
        if(root->val==target) {
            return true;
        }
        
        bool find1=search(root->left,target, s+='L');  // search on left side
        if(find1) return true;
        s.pop_back(); // backtracking step
        
        bool find2= search(root->right,target, s+='R'); // search on right side
        if(find2) return true;
        s.pop_back(); // backtracking step
        return false;
    }
  
     TreeNode* lca(TreeNode* root ,int n1 ,int n2)
    {
       if(root==NULL)
       return NULL;
       if(root->val==n1 or root->val==n2)
       return root;
       
       TreeNode* left=lca(root->left,n1,n2);
       TreeNode* right=lca(root->right,n1,n2);
       
       if(left!=NULL && right!=NULL)
       return root;
       if(left)
       return left;
       if(right)
       return right;
       
       return NULL; // not present in tree
       
    }
    string getDirections(TreeNode* root, int startValue, int destValue) {
        TreeNode* temp=lca(root,startValue,destValue);
        
        string s1,s2;
        search(temp,startValue,s1);
        search(temp,destValue,s2);
        for(auto &it:s1){
            it='U';
        }
        return s1+s2;
    }
};
var getDirections = function(root, startValue, destValue) {
    const getPath = (node, value, acc='') => {
        if (node === null) {
            return '';
        } else if (node.val === value) {
            return acc;
        } else {
            return getPath(node.left, value, acc + 'L') + getPath(node.right, value, acc + 'R')
        }
    }
    
	// generate the paths
    let startPath = getPath(root, startValue);
    let destPath = getPath(root, destValue);
    
    // find the lowest common ancestor
    let i = 0;
    for (; i < startPath.length && i < destPath.length && startPath[i] === destPath[i]; i++);
    
	// output the final path
    let output = '';
    for (let j = i; j < startPath.length; j++) {
        output += 'U';
    }
    
    return output + destPath.substring(i);
};
Step-By-Step Directions From a Binary Tree Node to Another