Leetcode 2096

# 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
from collections import deque, defaultdict
class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        g = defaultdict(list)

        def dfs(node):
            if node.left:
                g[node.val].append((node.left.val, "L"))
                g[node.left.val].append((node.val, "U"))
                dfs(node.left)
            if node.right:
                g[node.val].append((node.right.val, "R"))
                g[node.right.val].append((node.val, "U"))
                dfs(node.right)
        # build the graph
        dfs(root)

        # BFS to find shortest path
        q = deque()
        visited = set()
        # current postion, current path
        q.append((startValue, ""))
        visited.add(startValue)

        while q:
            currentPos, currentPath = q.popleft()

            if currentPos == destValue:
                return currentPath
            
            for child, direction in g[currentPos]:
                if child not in visited:
                    visited.add(child)
                    q.append((child, currentPath+direction))
        return ""