2096. Step-By-Step Directions From a Binary Tree Node to Another

 def BFS(graph,s,t):

    # Mark all the vertices as not visited

    visited = [False] * (len(graph)+1)

# Create a queue for BFS

    queue = []

    Parent=dict()

    # Mark the source node as

    # visited and enqueue it

    queue.append(s)

    visited[s] = True

 

    while queue:

        s = queue.pop(0)

        for i in graph[s]:

            if i !=0:

                if visited[i] == False:

                    Parent[i]=s

                    if i==t:

                        return Parent

                    queue.append(i)

                    visited[i] = True

    

class Solution:

    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:

        

        d=dict()

        parent=dict()

        

        parent[root.val]=0

        def inorder(root):

            if root:

                inorder(root.left)

                

                if root.left:

                    d[root.val]=[root.left.val]

                    parent[root.left.val]=root.val

                else:

                    d[root.val]=[0]

                    

                    

                if root.right:

                    d[root.val].append(root.right.val)

                    parent[root.right.val]=root.val

                else:

                    d[root.val].append(0)

                

                        

                

                inorder(root.right)

        inorder(root)

        

        

        

        # buildgraph

        graph=dict()

        for i in d.keys():

            if i in parent:

                graph[i]=d[i]+[parent[i]]

            else:

                graph[i]=d[i]

        

        #print(graph)

        

        # run bfs

        

        Parent=BFS(graph,startValue,destValue)

        

        #print(Parent)

        

        #find the relation 

        ans=""

        while destValue!=startValue:

                if Parent[destValue]==parent[destValue]:

                    if d[parent[destValue]][0]==destValue:

                        ans+="L"

                    if d[parent[destValue]][1]==destValue:

                        ans+="R"

                else:

                    ans+="U"

                destValue=Parent[destValue]

                

        return ans[::-1]