Iam_Sandeep

Min distance between two given nodes of a Binary Tree

Mar 23rd, 2022
1,264
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.17 KB | None | 0 0
  1. #User function Template for python3
  2. https://practice.geeksforgeeks.org/problems/min-distance-between-two-given-nodes-of-a-binary-tree/1
  3. '''
  4. # Node Class:
  5. class Node:
  6.    def __init__(self,val):
  7.        self.data = val
  8.        self.left = None
  9.        self.right = None
  10. '''
  11. class Solution:
  12.     def findDist(self,root,a,b):
  13.         ans=[None]
  14.         def dfs(x):
  15.             if not x:return 0,0
  16.             m,n=dfs(x.left)
  17.             p,q=dfs(x.right)
  18.             s=m or p or x.data==a
  19.             t=n or q or x.data==b
  20.             if s and t and  ans[0]==None:ans[0]=x
  21.             return s,t
  22.         def h(x,val):
  23.             q=deque()
  24.             q.append((x,0))
  25.             while q:
  26.                 for _ in range(len(q)):
  27.                     t,y=q.popleft()
  28.                     if t.data==val:return y
  29.                     if t.left:q.append((t.left,y+1))
  30.                     if t.right:q.append((t.right,y+1))
  31.         dfs(root)
  32.         res=h(ans[0],a)+h(ans[0],b)
  33.         return res
  34. #{
  35. #  Driver Code Starts
  36. #Initial Template for Python 3
  37.  
  38. import sys
  39. sys.setrecursionlimit(50000)
  40. from collections import deque
  41. # Tree Node
  42. class Node:
  43.     def __init__(self, val):
  44.         self.right = None
  45.         self.data = val
  46.         self.left = None
  47.  
  48. '''
  49. class Node:
  50.    def __init__(self, val):
  51.        self.right = None
  52.        self.data = val
  53.        self.left = None
  54. '''
  55.  
  56. # Function to Build Tree  
  57. def buildTree(s):
  58.     #Corner Case
  59.     if(len(s)==0 or s[0]=="N"):          
  60.         return None
  61.        
  62.     # Creating list of strings from input
  63.     # string after spliting by space
  64.     ip=list(map(str,s.split()))
  65.    
  66.     # Create the root of the tree
  67.     root=Node(int(ip[0]))                    
  68.     size=0
  69.     q=deque()
  70.    
  71.     # Push the root to the queue
  72.     q.append(root)                            
  73.     size=size+1
  74.    
  75.     # Starting from the second element
  76.     i=1                                      
  77.     while(size>0 and i<len(ip)):
  78.         # Get and remove the front of the queue
  79.         currNode=q[0]
  80.         q.popleft()
  81.         size=size-1
  82.        
  83.         # Get the current node's value from the string
  84.         currVal=ip[i]
  85.        
  86.         # If the left child is not null
  87.         if(currVal!="N"):
  88.            
  89.             # Create the left child for the current node
  90.             currNode.left=Node(int(currVal))
  91.            
  92.             # Push it to the queue
  93.             q.append(currNode.left)
  94.             size=size+1
  95.         # For the right child
  96.         i=i+1
  97.         if(i>=len(ip)):
  98.             break
  99.         currVal=ip[i]
  100.        
  101.         # If the right child is not null
  102.         if(currVal!="N"):
  103.            
  104.             # Create the right child for the current node
  105.             currNode.right=Node(int(currVal))
  106.            
  107.             # Push it to the queue
  108.             q.append(currNode.right)
  109.             size=size+1
  110.         i=i+1
  111.     return root
  112.  
  113.  
  114. if __name__=="__main__":
  115.     t=int(input())
  116.     for _ in range(0,t):
  117.         s=input()
  118.         root=buildTree(s)
  119.         a, b=map(int, input().split())
  120.         ob = Solution()
  121.         print(ob.findDist(root, a, b))
  122.  
  123. # } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment