Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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()
- # recursive method to display the binary tree in inorder
- def displayInorder(self,tempNode):
- if tempNode is None:
- return
- else:
- self.displayInorder(tempNode.getLeftNode())
- print(tempNode.getElement(), end=" ")
- self.displayInorder(tempNode.getRightNode())
- # method to display all Leaf nodes of the binary tree
- # traversing in inorder method and if both left and right links are null then we print the Leaf node
- def displayLeafNodes(self,tempNode):
- if tempNode is None:
- return
- self.displayLeafNodes(tempNode.getLeftNode())
- # check if it is a leaf node
- if tempNode.getLeftNode() is None and tempNode.getRightNode() is None:
- print(tempNode.getElement(), end=" ")
- self.displayLeafNodes(tempNode.getRightNode())
- # 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("\nThe inorder traversal of the BST is : ", end=" ")
- b1.displayInorder(root)
- print("\n\nThe Leaf Nodes of the BST are : ", end=" ")
- b1.displayLeafNodes(root)
Add Comment
Please, Sign In to add comment