m2skills

bst height python

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