Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # program to find the height of binary search tree
- class node:
- # constructor method
- # setting default value of left and right links to null
- def __init__(self,element,left = None,right = None):
- self.element = element
- self.left = left
- self.right = right
- # method to update left Link
- def updateLeftLink(self,link):
- self.left = link
- # method to update right link
- def updateRightLink(self,link):
- self.right = link
- # method to get the data element of the node
- def getElement(self):
- return self.element
- # method to get the Left node
- def getLeftNode(self):
- return self.left
- # method to get the right node
- def getRightNode(self):
- return self.right
- class BST:
- def __init__(self):
- self.root = None
- self.pHeight = 0
- # method returns true if the bst is empty
- def isEmpty(self):
- return self.root is None
- # method returns root of the binary search tree
- def getRoot(self):
- return self.root
- # method inserts element in the binary search tree
- def insert(self,element):
- tempNode = node(element)
- if self.getRoot() is None:
- self.root = tempNode
- else:
- inserted = False
- p = self.root
- while not inserted:
- # if new element is greater the current element then insert it to the right
- if tempNode.getElement() > p.getElement():
- # if right link of the current is null then directly insert
- if p.getRightNode() is None:
- p.updateRightLink(tempNode)
- inserted = True
- else:
- p = p.getRightNode()
- # if new element is less the current element then insert it to the left
- elif tempNode.getElement() < p.getElement():
- # if left link of the current is null then directly insert
- if p.getLeftNode() is None:
- p.updateLeftLink(tempNode)
- inserted = True
- else:
- p = p.getLeftNode()
- # this function resets the tree height and then calls the height function
- def height(self):
- self.pHeight = 0
- return self.height_helper(self.root, 0)
- # method to find the height of the binary search tree
- def height_helper(self,tempNode,tempHeight):
- if tempNode is None:
- return 0
- else:
- tempHeight = self.height_helper(tempNode.getLeftNode(), tempHeight)
- tempHeight += 1
- if tempNode == self.root:
- if self.pHeight < tempHeight:
- self.pHeight = tempHeight
- tempHeight = 0
- tempHeight = self.height_helper(tempNode.getRightNode(), tempHeight)
- if tempNode == self.root:
- if self.pHeight < tempHeight:
- self.pHeight = tempHeight
- tempHeight = 0
- return self.pHeight + 1
- # main function
- b1 = BST()
- b1.insert(7)
- b1.insert(29)
- b1.insert(25)
- b1.insert(36)
- b1.insert(71)
- b1.insert(24)
- b1.insert(5)
- b1.insert(9)
- b1.insert(1)
- root = b1.getRoot()
- print("\n\nThe height of the binary search tree is : " + str(b1.height()))
Add Comment
Please, Sign In to add comment