Untitled

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        # Use DFS to find the path from root to target
        def dfs(node: Optional[TreeNode], target: int, path: List[str]) -> bool:
            if not node:
                return False

            if node.val == target:
                return True
            
            # We first check if we found the target and then append the path
            # This means we only accumulate the path when stackframes are popping/returning
            # This causes the path to be reversed (target-to-root)
            if dfs(node.left, target, path):
                path += "L"
            elif dfs(node.right, target, path):
                path += "R"
            
            return len(path) > 0
        
        startPath, destPath = [], []
        dfs(root, startValue, startPath)
        dfs(root, destValue, destPath)

        # We now have target-to-root paths from each of start and destination
        # That means movements from root are at the end of the path
        # We can remove redundant movements
        # This is effectively pruning common ancestors until we find the lowest
        while len(startPath) > 0 and len(destPath) > 0 and startPath[-1] == destPath[-1]:
            startPath.pop()
            destPath.pop()

        # Now, we join together the two paths
        # Every movement in the start path is just an 'up' direction
        # We keep the movements in the destination path (reversing for root-to-target)
        up = "".join("U" * len(startPath))
        down = "".join(reversed(destPath))
        return up + down