BST python

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