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]
