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

<p>Find the <strong>shortest path</strong> starting from node <code>s</code> and ending at node <code>t</code>. Generate step-by-step directions of such path as a string consisting of only the <strong>uppercase</strong> letters <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, and <code>&#39;U&#39;</code>. Each letter indicates a specific direction:</p>

<ul>
	<li><code>&#39;L&#39;</code> means to go from a node to its <strong>left child</strong> node.</li>
	<li><code>&#39;R&#39;</code> means to go from a node to its <strong>right child</strong> node.</li>
	<li><code>&#39;U&#39;</code> means to go from a node to its <strong>parent</strong> node.</li>
</ul>

<p>Return <em>the step-by-step directions of the <strong>shortest path</strong> from node </em><code>s</code><em> to node</em> <code>t</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg1.png" style="width: 214px; height: 163px;" />
<pre>
<strong>Input:</strong> root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
<strong>Output:</strong> &quot;UURL&quot;
<strong>Explanation:</strong> The shortest path is: 3 &rarr; 1 &rarr; 5 &rarr; 2 &rarr; 6.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg2.png" style="width: 74px; height: 102px;" />
<pre>
<strong>Input:</strong> root = [2,1], startValue = 2, destValue = 1
<strong>Output:</strong> &quot;L&quot;
<strong>Explanation:</strong> The shortest path is: 2 &rarr; 1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is <code>n</code>.</li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= Node.val &lt;= n</code></li>
	<li>All the values in the tree are <strong>unique</strong>.</li>
	<li><code>1 &lt;= startValue, destValue &lt;= n</code></li>
	<li><code>startValue != destValue</code></li>
</ul>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 find common ancestor of start node and dest node 
 find depth of start node from common ancestor. The 'U' character would be appended depth number of times
 find the path of dest node from common ancestor
 */
class Solution {
public:
    bool findPath(TreeNode* root, int key, vector<TreeNode*> &path){
        path.push_back(root);

        // if key found return true;
        if(root->val == key) return true;
        // if key in left or right subtree return true;
        if((root->left && findPath(root->left, key, path)) || (root->right && findPath(root->right, key, path))) return true;

        path.pop_back();
        return false;
    }
    void findDepth(TreeNode* root, int destValue, int currDepth, int &depth){
        if(root->val == destValue){
            depth = currDepth;
            return;
        }

        if(depth == -1 && root->left) findDepth(root->left, destValue ,currDepth + 1, depth);
        if(depth == -1 && root->right) findDepth(root->right, destValue ,currDepth + 1, depth);
    }
    void findPathtoDest(TreeNode* root, int destValue, bool &isFound, string &ans){
        if(root -> val == destValue){
            isFound = true;
            return;
        }

        if(!isFound && root->left){
            ans.push_back('L');
            findPathtoDest(root->left, destValue, isFound, ans);
            if(!isFound) ans.pop_back();
        }
        if(!isFound && root->right){
            ans.push_back('R');
            findPathtoDest(root->right, destValue, isFound, ans);
            if(!isFound) ans.pop_back();
        }
    }
    string getDirections(TreeNode* root, int startValue, int destValue) {
        vector<TreeNode*> pathStart, pathDest;
        findPath(root, startValue, pathStart);
        findPath(root, destValue, pathDest);

        int i = 0;
        while(i < pathStart.size() && i < pathDest.size()){
            if(pathStart[i] != pathDest[i])break;
            i++;
        }
        TreeNode* LCA = pathStart[i-1];

        int depth = pathStart.size() - (i-1) - 1;
        string ans = "";
        for(int i = 0; i < depth; i++){
            ans+='U';
        }
        bool isFound = false;
        findPathtoDest(LCA, destValue, isFound, ans);
        return ans;
    }
};
145873