document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  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.     # recursive method to display the binary tree in inorder
  79.     def displayInorder(self,tempNode):
  80.         if tempNode is None:
  81.             return
  82.         else:
  83.             self.displayInorder(tempNode.getLeftNode())
  84.             print(tempNode.getElement(), end="  ")
  85.             self.displayInorder(tempNode.getRightNode())
  86.  
  87.  
  88.     # method to display all Leaf nodes of the binary tree
  89.     # traversing in inorder method and if both left and right links are null then we print the Leaf node
  90.     def displayLeafNodes(self,tempNode):
  91.         if tempNode is None:
  92.             return
  93.  
  94.         self.displayLeafNodes(tempNode.getLeftNode())
  95.  
  96.         # check if it is a leaf node
  97.         if tempNode.getLeftNode() is None and tempNode.getRightNode() is None:
  98.             print(tempNode.getElement(), end="  ")
  99.  
  100.         self.displayLeafNodes(tempNode.getRightNode())
  101.  
  102.  
  103. # main function
  104.  
  105. b1 = BST()
  106. b1.insert(7)
  107. b1.insert(29)
  108. b1.insert(25)
  109. b1.insert(36)
  110. b1.insert(71)
  111. b1.insert(24)
  112. b1.insert(5)
  113. b1.insert(9)
  114. b1.insert(1)
  115.  
  116. root = b1.getRoot()
  117.  
  118. print("\\nThe inorder traversal of the BST is : ", end=" ")
  119. b1.displayInorder(root)
  120.  
  121. print("\\n\\nThe Leaf Nodes of the BST are : ", end=" ")
  122. b1.displayLeafNodes(root)
');