# PROGRAM TO IMPLEMENT BINARY SEARCH TREE IN PYTHON
import time
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
self.myList = []
# 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())
# recursive method to display the binary tree in preorder
def displayPreorder(self,tempNode):
if tempNode is None:
return
else:
print(tempNode.getElement(), end=" ")
self.displayPreorder(tempNode.getLeftNode())
self.displayPreorder(tempNode.getRightNode())
# recursive method to display binary tree in postorder
def displayPostorder(self,tempNode):
if tempNode is None:
return
else:
self.displayPostorder(tempNode.getLeftNode())
self.displayPostorder(tempNode.getRightNode())
print(tempNode.getElement(), end=" ")
# 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())
# method to display the max element of the Binary Tree
# max element is the rightmost node of the bst
def maxElement(self):
# check if the bst is empty or not
if self.isEmpty():
return -999999 # assuming that -999999 never appears in the BST
tempNode = self.getRoot()
# traverse to the rightmost node in the bst
while tempNode.getRightNode() is not None:
tempNode = tempNode.getRightNode()
return tempNode.getElement()
# method to display the min element of the Binary Tree
# min element is the leftmost node of the bst
def minElement(self):
# check if the bst is empty or not
if self.isEmpty():
return 999999 # assuming that 999999 never appears in the BST
tempNode = self.getRoot()
# traverse to the rightmost node in the bst
while tempNode.getLeftNode() is not None:
tempNode = tempNode.getLeftNode()
return tempNode.getElement()
# method to find the common ancestor of 2 nodes
# method assumes that both the nodes are already present in the binary tree
def commonAncestor(self, e1, e2):
tempNode = self.getRoot()
parent = self.getRoot()
found = False
while not found:
data = tempNode.getElement()
# if both the elements are greater than the data then traverse right
if data < e1 and data < e2:
parent = tempNode
tempNode = tempNode.getRightNode()
# if the element are less than data traverse left
elif data > e1 and data > e2:
parent = tempNode
tempNode = tempNode.getLeftNode()
# if one of the element is equal to the data then the parent node is the required Ancestor
elif data == e1 or data == e2:
print("\\nThe common Ancestor of " + str(e1) + " and " + str(e2) + " is " + str(parent.getElement()))
found = True
# if one element is greater and other is smaller then current node is the required ancestor
else:
print("\\nThe common Ancestor of " + str(e1) + " and " + str(e2) + " is " + str(tempNode.getElement()))
found = True
# method to search an element in the binary search tree
# if found method returns true
def search(self, element):
# if the bst is empty return false
if self.isEmpty():
return False
tempNode = self.getRoot()
found = False
while not found:
# if tempNode is null then the element is not present
# break out of the loop
if tempNode is None:
break
# if the element are less than current data traverse right
if tempNode.getElement() > element:
tempNode = tempNode.getLeftNode()
# if the element are greater than current data traverse left
elif tempNode.getElement() < element:
tempNode = tempNode.getRightNode()
# if the element is equal to the current data then set found to true
elif tempNode.getElement() == element:
found = True
return found
# method to display all nodes at a distance k from the root of the binary tree
# traversing in preorder method and if distance of node is k then we print the node
def displayNodesAtDistance(self,tempNode, distance, count):
if tempNode is None:
return
if count > distance:
return
if count == distance:
print(tempNode.getElement())
self.displayNodesAtDistance(tempNode.getLeftNode(), distance, count + 1)
self.displayNodesAtDistance(tempNode.getRightNode(), distance, count + 1)
# 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
# method to delete an element from the binary search tree
def deleteElement(self, element):
removed = False
tempNode = self.getRoot()
parent = self.getRoot()
while not removed:
if tempNode.getElement() > element:
parent = tempNode
tempNode = tempNode.getLeftNode()
elif tempNode.getElement() < element:
parent = tempNode
tempNode = tempNode.getRightNode()
elif tempNode.getElement() == element:
parentData = parent.getElement()
nodeData = tempNode.getElement()
# checking if the node is a leaf node
if tempNode.getLeftNode() is None and tempNode.getRightNode() is None:
if parentData > nodeData:
parent.updateLeftLink(None)
elif parentData < nodeData:
parent.updateRightLink(None)
removed = True
del tempNode
# checking if the node has only a left subtree
elif tempNode.getLeftNode() is not None and tempNode.getRightNode() is None:
if parentData > nodeData:
parent.updateLeftLink(tempNode.getLeftNode())
elif parentData > nodeData:
parent.updateRightLink(tempNode.getLeftNode())
del tempNode
removed = True
# checking is the node has only a right subtree
elif tempNode.getLeftNode() is None and tempNode.getRightNode() is not None:
if parentData > nodeData:
parent.updateLeftLink(tempNode.getRightNode())
elif parent.getElement() > tempNode.getElement():
parent.updateRightLink(tempNode.getRightNode())
del tempNode
removed = True
# checking if the node to ne deleted is the root node
elif self.getRoot().getElement() == tempNode.getElement():
if tempNode.getLeftNode() is None:
self.root = tempNode.getRightNode()
elif tempNode.getRightNode() is None:
self.root = tempNode.getLeftNode()
else:
q = tempNode.getRightNode()
self.root = q
r = tempNode.getLeftNode()
while q.getLeftNode() is not None:
q = q.getLeftNode()
q.updateLeftLink(r)
del tempNode
removed = True
elif tempNode.getLeftNode() is None and tempNode.getRightNode() is None:
if parentData > nodeData:
parent.updateLeftLink(tempNode.getRightNode())
elif parentData < nodeData:
parent.updateRightLink(tempNode.getRightNode())
q = tempNode.getLeftNode()
r = tempNode.getRightNode()
while r.getLeftNode() is not None:
r = r.getLeftNode()
r.updateLeftLink(q)
del tempNode
removed = True
def deleteMin(self):
element = self.minElement()
self.deleteElement(element)
def deleteMax(self):
element = self.maxElement()
self.deleteElement(element)
# 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 Preorder traversal of the BST is : ", end=" ")
b1.displayPreorder(root)
print("\\n\\nThe Postorder traversal of the BST is : ", end=" ")
b1.displayPostorder(root)
print("\\n\\nThe Leaf Nodes of the BST are : ", end=" ")
b1.displayLeafNodes(root)
print("\\n\\nThe Largest Element of the BST is : " + str(b1.maxElement()))
print("\\nThe Smallest Element of the BST is : " + str(b1.minElement()))
# b1.deleteMax()
# b1.deleteMin()
print("\\n\\nThe Inorder traversal of the BST is : ", end=" ")
b1.displayInorder(root)
b1.commonAncestor(6,1)
b1.commonAncestor(1,9)
b1.commonAncestor(9,36)
print("\\n\\nNodes at a distance 2 from the root node are : ")
b1.displayNodesAtDistance(root,2,0)
print("\\n")
# searching for the elements in the binary search tree
print(b1.search(25))
print(b1.search(37))
print("\\n\\nThe height of the binary search tree is : " + str(b1.height()))
b1.deleteElement(36)
b1.deleteMin()
b1.deleteMax()
print("\\nThe Breadth First Traversal of the BST is :", end = " ")
b1.bfs()
print("\\nThe inorder traversal of the BST is : ", end=" ")
b1.displayInorder(root)
print()
b1.kthSmallest(root,3)