Binary Search Tree

Initiate the class

class BST:
    def __init__(self,value):
        self.value = value
        self.left = None
        self.right = None

Insert a value into the tree

# Average O(log(n)) time | O(1) space
# Worst O(n) time | O(1) space - In case of a tree with single branch
    def insert(self,value):
        currentNode = self
        while True:      
            if value < currentNode.value:
                # If the value to be inserted is less then the current node's value
                # and the left node is None, then insert the value there
                # If the left node is not none, the current node is the left node  
                if currentNode.left is None:
                    currentNode.left = BST(value)
                    break
                else:
                    currentNode = currentNode.left

            else:
                # This is when the value to be inserted is greater than the current node's value
                if currentNode.right is None:
                    currentNode.right = BST(value)
                    break
                else:
                    currentNode = currentNode.right
        return self

Search for a value in the tree

# Average O(log(n)) time | O(1) space
# Worst O(n) time | O(1) space
    def contains(self,value):
        currentNode = self
        while currentNode is not None:
            if value < currentNode.value:
                currentNode = currentNode.left
            elif value > currentNode.value:
                currentNode = currentNode.right
            else:
                return True
        return False

Remove a value from the tree

# Average O(log(n)) time | O(1) space
# Worst O(n) time | O(1) space
    def remove(self,value):
        currentNode = self
        while currentNode is not None:
            if value < currentNode.value:
                parentNode = currentNode
                currentNode = currentNode.left
            elif value > currentNode.value:
                parentNode = currentNode
                currentNode = currentNode.right
            else:
                # When value is equal to currentNode.value
                if currentNode.left is not None and currentNode.right is not None:
                    # when both left and right nodes are not None
                    # find the node with the minimum value in the right subtree
                    # and replace the value of the node with the minimum value
                    # remove the minimum value from the right subtree
                    currentNode.value = currentNode.right.getMinValue()
                    currentNode.right.remove(currentNode.value, currentNode)
                elif parentNode is None:
                    # When currentNode is the root node
                    if currentNode.left is not None:                                                                        
                        currentNode.value = currentNode.left.value
                        currentNode.right = currentNode.left.right
                        currentNode.left = currentNode.left.left
                    elif currentNode.right is not None:
                        currentNode.value = currentNode.right.value
                        currentNode.left = currentNode.right.left
                        currentNode.right = currentNode.right.right
                    else:
                        currentNode.value = None
                elif parentNode.left = currentNode:
                    parentNode.left = currentNode.left if currentNode.left is not None else currentNode.right
                elif parentNode.right = currentNode:
                    parentNode.right = currentNode.left if currentNode.left is not None else currentNode.right
                break
        return self

    def getMinValue(self):
        currentNode = self
        while currentNode.left is not None:
            currentNode = currentNode.left
        return currentNode.value