A binary search tree stores smaller values in the left subtree and larger values in the right subtree. The example below shows the three standard operations: lookup, insertion, and deletion. The deletion routine covers the three usual cases: no children, one child, or two children.

class TreeNode: def init(self, value): self.value = value self.left = None self.right = None

def contains(node, target): # Walk downward until the value is found or the branch ends. while node is not None: if target == node.value: return True if target < node.value: node = node.left else: node = node.right return False

def insert(node, value): # Create a new leaf when the search path reaches an empty spot. if node is None: return TreeNode(value)

if value < node.value:
    node.left = insert(node.left, value)
elif value > node.value:
    node.right = insert(node.right, value)

return node

def leftmost(node): # The minimum value in a subtree is stored at the far left. current = node while current is not None and current.left is not None: current = current.left return current

def remove(node, value): # Stop when the subtree is empty. if node is None: return None

if value < node.value:
    node.left = remove(node.left, value)
elif value > node.value:
    node.right = remove(node.right, value)
else:
    # Case 1: no left child
    if node.left is None:
        return node.right

    # Case 2: no right child
    if node.right is None:
        return node.left

    # Case 3: two children, replace with the in-order successor.
    successor = leftmost(node.right)
    node.value = successor.value
    node.right = remove(node.right, successor.value)

return node

def inorder(node): # Useful for checking that the tree still remains sorted. if node is not None: inorder(node.left) print(node.value, end=" ") inorder(node.right)