LC 2096 [M] Step By Step Directions From a Binary Tree Node to Another - ALawliet/algorithms GitHub Wiki

# 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:
        def getLCA(node):
            if not node:
                return
            if node.val in (startValue, destValue):
                return node
            left, right = getLCA(node.left), getLCA(node.right)
            if left and right:
                return node
            return left or right
        
        lca = getLCA(root)
        lcaToStart = lcaToDest = None
        Q = deque([ (lca, '') ])
        while Q:
            node, path = Q.popleft()
            
            # goal
            if node.val == startValue:
                lcaToStart = path
            if node.val == destValue:
                lcaToDest = path
            if lcaToStart and lcaToDest: break
                    
            if node.left:
                Q.append( (node.left, path+'L') )
            if node.right:
                Q.append( (node.right, path+'R') )
                
        return 'U'*len(lcaToStart) + lcaToDest