Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #User function Template for python3
- https://practice.geeksforgeeks.org/problems/min-distance-between-two-given-nodes-of-a-binary-tree/1
- '''
- # Node Class:
- class Node:
- def __init__(self,val):
- self.data = val
- self.left = None
- self.right = None
- '''
- class Solution:
- def findDist(self,root,a,b):
- ans=[None]
- def dfs(x):
- if not x:return 0,0
- m,n=dfs(x.left)
- p,q=dfs(x.right)
- s=m or p or x.data==a
- t=n or q or x.data==b
- if s and t and ans[0]==None:ans[0]=x
- return s,t
- def h(x,val):
- q=deque()
- q.append((x,0))
- while q:
- for _ in range(len(q)):
- t,y=q.popleft()
- if t.data==val:return y
- if t.left:q.append((t.left,y+1))
- if t.right:q.append((t.right,y+1))
- dfs(root)
- res=h(ans[0],a)+h(ans[0],b)
- return res
- #{
- # Driver Code Starts
- #Initial Template for Python 3
- import sys
- sys.setrecursionlimit(50000)
- from collections import deque
- # Tree Node
- class Node:
- def __init__(self, val):
- self.right = None
- self.data = val
- self.left = None
- '''
- class Node:
- def __init__(self, val):
- self.right = None
- self.data = val
- self.left = None
- '''
- # Function to Build Tree
- def buildTree(s):
- #Corner Case
- if(len(s)==0 or s[0]=="N"):
- return None
- # Creating list of strings from input
- # string after spliting by space
- ip=list(map(str,s.split()))
- # Create the root of the tree
- root=Node(int(ip[0]))
- size=0
- q=deque()
- # Push the root to the queue
- q.append(root)
- size=size+1
- # Starting from the second element
- i=1
- while(size>0 and i<len(ip)):
- # Get and remove the front of the queue
- currNode=q[0]
- q.popleft()
- size=size-1
- # Get the current node's value from the string
- currVal=ip[i]
- # If the left child is not null
- if(currVal!="N"):
- # Create the left child for the current node
- currNode.left=Node(int(currVal))
- # Push it to the queue
- q.append(currNode.left)
- size=size+1
- # For the right child
- i=i+1
- if(i>=len(ip)):
- break
- currVal=ip[i]
- # If the right child is not null
- if(currVal!="N"):
- # Create the right child for the current node
- currNode.right=Node(int(currVal))
- # Push it to the queue
- q.append(currNode.right)
- size=size+1
- i=i+1
- return root
- if __name__=="__main__":
- t=int(input())
- for _ in range(0,t):
- s=input()
- root=buildTree(s)
- a, b=map(int, input().split())
- ob = Solution()
- print(ob.findDist(root, a, b))
- # } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment