Step-by-step directions from a binary tree to another

/**
 * 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) {}
 * };
 */

//LOGIC:We will find LCA and then find path between LCA to start_node and LCA to end_node so start_node to LCA path will be only UP
//wo we pushed in answer string only U for path length from start_node to LCA and then pushed path from LCA to end.
//Time complexity:O(3N)
//follow method2 for O(N)
class Solution {
    TreeNode* LCA(TreeNode* root,int startValue,int destValue){
        if(root==NULL || root->val==startValue || root->val==destValue)
            return root;

        TreeNode* l=LCA(root->left,startValue,destValue);
        TreeNode* r=LCA(root->right,startValue,destValue);

        if(l==NULL)  // It means we didn't get anything in left so if left have something, return it else null.
            return r;

        if(r==NULL)  //It means that l is having some because it came to this if statement by not following the conditional
            return l; //statement of previous if so l have some,so return it.

        return root;  //It means l and r both have something because control came to this line by rejecting conditional
                      //statement of both of the above if so it is LCS so return it.
    }

    bool shortestPath(TreeNode* node,int key,string &s,char dir){
        if(node==NULL){
            return 0;
        }

        if(node->val==key){
            s.push_back(dir);
            return 1;
        }

        s.push_back(dir);

        if(shortestPath(node->left,key,s,'L')){
            return 1;
        }

        if(shortestPath(node->right,key,s,'R')){
            return 1;
        }
        s.pop_back();   //If path is not possible with this node,then pop the current node also
        return 0;
    }
public:
    string getDirections(TreeNode* root, int startValue, int destValue) {
        if(root==NULL)
            return {};

        TreeNode* node=LCA(root,startValue,destValue);
        string start,end;

        shortestPath(node,startValue,start,'-1');

        shortestPath(node,destValue,end,'-1');


        if(start.size()==0)
            return end;

        string ans;
        for(int i=1;i<start.size();i++){  //because from left node it will be always up till the LCA
            ans+='U';
        }

         for(int i=1;i<end.size();i++){
            ans+=end[i];
        }
        return ans;
    }
};

//Method2:
//logic:we find the path from actual root to start_value then actual root to end_value and popped the path until LCA is achieved.
//then start_node to lca path will be always up so added U in answer string and LCA path to end_value added in answer string.
/*
#include <bits/stdc++.h>
using namespace std;

// Structure of Tree
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val2)
    {
        val = val2;
        left = NULL;
        right = NULL;
    }
};

// Find Function
bool find(TreeNode* n, int val,string& path)
{
    if (n->val == val)
        return true;
    if (n->left && find(n->left,
                        val, path)) {
        path.push_back('L');
        return true;
    }
    if (n->right && find(n->right, val, path)) {
        path.push_back('R');
        return true;
    }
    return false;  //If you couldn't find the node from both left and right subtree then answer can't be with this node.
}

// Function to keep track
// of directions at any point
string getDirections(TreeNode* root, int startValue, int destValue)
{
    // To store the startPath and destPath
    string s_p, d_p;
    find(root, startValue, s_p); //It will have path from bottom to top or startValue to top.
    find(root, destValue, d_p);  //It will also have path from bottom or top to destValue to top.

    while (!s_p.empty() && !d_p.empty() && s_p.back() == d_p.back()) { //search from top till the path going same or till LCS
        s_p.pop_back();
        d_p.pop_back();
    }

    for (int i = 0; i < s_p.size(); i++) {
        s_p[i] = 'U';
    }
    reverse(d_p.begin(), d_p.end());
    string ans = s_p + d_p;
    return ans;
}

// Driver Code
int main()
{
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(1);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(4);

    int startValue = 3;
    int endValue = 6;

    // Function Call
    string ans = getDirections(root, startValue, endValue);

    // Print the result
    cout << ans;
}
*/