Create a new version of paste:

# 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)