class Node:
    def __init__(self, value):

        # node properties
        self.left = None
        self.right = None
        self.value = value


class BinarySearchTree:
    def __init__(self):

        # define root node
        self.root = None


    def insert(self, value):

        # create new node
        newNode = Node(value)

        # if root node does not exist, assign new node as root
        if self.root is None:
            self.root = newNode
        else:

            # Keep track of current node
            currentNode = self.root

            # Traverse tree
            while True:

                # Add new node to the left if value is less than current node's value. Otherwise add to right side
                if value < currentNode.value:

                    # Check if current node has left child
                    # If empty, add new node
                    if currentNode.left is None:

                        currentNode.left = newNode
                        return newNode

                    currentNode = currentNode.left

                else:

                     # Check if current node has right child
                     # If empty, add new node
                    if currentNode.right is None:
                        currentNode.right = newNode
                        return newNode

                    currentNode = currentNode.right


    def lookup(self, value):

        # Check if root node exists
        if self.root is None:
            return False

        # Keep track of current node
        currentNode = self.root

        # Traverse tree
        while currentNode:

            # If lookup value is less than current node's value, traverse left else traverse right. Update the current node
            # If current node's value equals the look up value, return the node
            if value < currentNode.value:
                currentNode = currentNode.left
            elif value > currentNode.value:
                currentNode = currentNode.right
            elif value == currentNode.value:
                print(True)
                return currentNode

        # return None if lookup value not found
        return None

    def remove(self, root, key):

        if not root:
            return

        # we always want to delete the node when it is the root of a subtree,
        # so we handle left or right according to the val.
        # if the node does not exist, we will hit the very first if statement and return None.
        if key > root.val:
            root.right = self.remove(root.right, key)

        elif key < root.val:
            root.left = self.remove(root.left, key)

        # now the key is the root of a subtree
        else:
            # if the subtree does not have a left child, we just return its right child
            # to its father, and they will be connected on the higher level recursion.
            if not root.left:
                return root.right

            # if it has a left child, we want to find the max val on the left subtree to
            # replace the node we want to delete.
            else:
                # try to find the max value on the left subtree
                tmp = root.left
                while tmp.right:
                    tmp = tmp.right

                # replace
                root.val = tmp.val
                root.left = self.remove(root.left, tmp.val)

        return root

tree = BinarySearchTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.remove(tree, 20)