Deleting, and Why Balance Matters

Deleting: three cases

• No children (a leaf): just remove it.
• One child: replace the node with its child.
• Two children: copy in the next bigger value (the smallest value in the right subtree), then delete that value from the right subtree.

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

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

def delete(node, value):
    if node is None:
        return None
    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        nxt = node.right
        while nxt.left:
            nxt = nxt.left
        node.value = nxt.value
        node.right = delete(node.right, nxt.value)
    return node

def inorder(node):
    return [] if node is None else inorder(node.left) + [node.value] + inorder(node.right)

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)
for v in [20, 30, 50]:
    root = delete(root, v)
    print("after deleting", v, ":", inorder(root), "root is", root.value)

Output

after deleting 20 : [30, 40, 50, 60, 70, 80] root is 50
after deleting 30 : [40, 50, 60, 70, 80] root is 50
after deleting 50 : [40, 60, 70, 80] root is 60

Balance matters

Insert values that are already sorted and every new node goes to the right. The “tree” becomes a long line, and searching is O(n) again:

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

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

def height(node):
    return 0 if node is None else 1 + max(height(node.left), height(node.right))

mixed, line = None, None
for v in [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]:
    mixed = insert(mixed, v)
for v in range(1, 16):
    line = insert(line, v)
print("15 values, mixed order -> height", height(mixed))
print("15 values, sorted order -> height", height(line))

Output

15 values, mixed order -> height 4
15 values, sorted order -> height 15

Remember: Self-balancing trees (AVL trees, red-black trees) fix this automatically by rotating nodes, so their height always stays O(log n). Libraries use them for sorted maps and sets.

Tip: Python has no built-in BST. When you need sorted data with fast lookups, a sorted list + bisect or a dict is usually enough.