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)
def LCA(root, startValue, destValue):
    if root is None or root.val == startValue or root.val == destValue:
        return root

    l = LCA(root.left, startValue, destValue)
    r = LCA(root.right, startValue, destValue)

    if l is None:  # It means we didn't get anything in left so if left have something, return it else null.
        return r

    if r is None:  # 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.


def shortestPath(node, key, s, dir):
    if node is None:
        return False

    if node.val == key:
        s.append(dir)
        return True

    s.append(dir)

    if shortestPath(node.left, key, s, 'L'):
        return True

    if shortestPath(node.right, key, s, 'R'):
        return True

    s.pop()   # If path is not possible with this node,then pop the current node also
    return False


class Solution:
    def getDirections(self, root, startValue, destValue):
        if root is None:
            return ""

        node = LCA(root, startValue, destValue)
        start = []
        end = []

        shortestPath(node, startValue, start, '-')  # Python does not support multi-char char literal

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

        if len(start) == 0:
            return "".join(end)

        ans = []

        for i in range(1, len(start)):  # because from left node it will be always up till the LCA
            ans.append('U')

        for i in range(1, len(end)):
            ans.append(end[i])

        return "".join(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.
/*
# Find Function
def find(n, val, path):
    if n.val == val:
        return True

    if n.left and find(n.left, val, path):
        path.append('L')
        return True

    if n.right and find(n.right, val, path):
        path.append('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.


class Solution:

    # Function to keep track
    # of directions at any point
    def getDirections(self, root, startValue, destValue):

        # To store the startPath and destPath
        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.

        # search from top till the path going same or till LCS
        while s_p and d_p and s_p[-1] == d_p[-1]:
            s_p.pop()
            d_p.pop()

        for i in range(len(s_p)):
            s_p[i] = 'U'

        d_p.reverse()

        ans = "".join(s_p) + "".join(d_p)
        return ans