m2skills

common ancestor bst python

May 31st, 2017
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.15 KB | None | 0 0
  1. class node:
  2.    
  3.     # constructor method
  4.     # setting default value of left and right links to null
  5.     def __init__(self,element,left = None,right = None):
  6.         self.element = element
  7.         self.left = left
  8.         self.right = right
  9.  
  10.  
  11.     # method to update left Link   
  12.     def updateLeftLink(self,link):
  13.         self.left = link
  14.  
  15.  
  16.     # method to update right link  
  17.     def updateRightLink(self,link):
  18.         self.right = link  
  19.  
  20.  
  21.     # method to get the data element of the node
  22.     def getElement(self):
  23.         return self.element
  24.  
  25.     # method to get the Left node  
  26.     def getLeftNode(self):
  27.         return self.left
  28.    
  29.     # method to get the right node
  30.     def getRightNode(self):
  31.         return self.right  
  32.  
  33.  
  34. class BST:
  35.     def __init__(self):
  36.         self.root = None
  37.         self.pHeight = 0
  38.    
  39.    
  40.     # method returns true if the bst is empty
  41.     def isEmpty(self):
  42.         return self.root is None
  43.  
  44.     # method returns root of the binary search tree
  45.     def getRoot(self):
  46.         return self.root
  47.    
  48.    
  49.     # method inserts element in the binary search tree 
  50.     def insert(self,element):
  51.         tempNode = node(element)
  52.        
  53.         if self.getRoot() is None:
  54.             self.root = tempNode
  55.         else:
  56.             inserted = False
  57.             p = self.root
  58.             while not inserted:
  59.                 # if new element is greater the current element then insert it to the right
  60.                 if tempNode.getElement() > p.getElement():
  61.                     # if right link of the current is null then directly insert
  62.                     if p.getRightNode() is None:
  63.                         p.updateRightLink(tempNode)
  64.                         inserted = True
  65.                     else:
  66.                         p = p.getRightNode()
  67.                
  68.                 # if new element is less the current element then insert it to the left
  69.                 elif tempNode.getElement() < p.getElement():
  70.                     # if left link of the current is null then directly insert
  71.                     if p.getLeftNode() is None:
  72.                         p.updateLeftLink(tempNode)
  73.                         inserted = True
  74.                     else:
  75.                         p = p.getLeftNode()
  76.                    
  77.    
  78.     # method to find the common ancestor of 2 nodes
  79.     # method assumes that both the nodes are already present in the binary tree
  80.     def commonAncestor(self, e1, e2):
  81.        
  82.         tempNode = self.getRoot()
  83.         parent = self.getRoot()
  84.        
  85.         found = False
  86.         while not found:
  87.             data = tempNode.getElement()
  88.             # if both the elements are greater than the data then traverse right
  89.             if data < e1 and data < e2:
  90.                 parent = tempNode
  91.                 tempNode = tempNode.getRightNode()
  92.  
  93.             # if the element are less than data traverse left  
  94.             elif data > e1 and data > e2:
  95.                 parent = tempNode
  96.                 tempNode = tempNode.getLeftNode()
  97.                
  98.             # if one of the element is equal to the data then the parent node is the required Ancestor 
  99.             elif data == e1 or data == e2:
  100.                 print("\nThe common Ancestor of " + str(e1) + " and " + str(e2) + " is " + str(parent.getElement()))
  101.                 found = True
  102.            
  103.             # if one element is greater and other is smaller then current node is the required ancestor
  104.             else:
  105.                 print("\nThe common Ancestor of " + str(e1) + " and " + str(e2) + " is " + str(tempNode.getElement()))
  106.                 found = True
  107.            
  108. # main function
  109.  
  110. b1 = BST()
  111. b1.insert(7)
  112. b1.insert(29)
  113. b1.insert(25)
  114. b1.insert(36)
  115. b1.insert(71)
  116. b1.insert(24)
  117. b1.insert(5)
  118. b1.insert(9)
  119. b1.insert(1)
  120.  
  121. root = b1.getRoot()
  122.  
  123. b1.commonAncestor(6,1)
  124. b1.commonAncestor(1,9)
  125. b1.commonAncestor(9,36)
Add Comment
Please, Sign In to add comment