Binary search trees & balancing

Fast lookups like an array, fast inserts like a linked list.

The idea

A Binary Search Tree (BST) enforces a strict rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This allows us to cut the search space in half at every step, just like binary search.

However, if you insert already-sorted data (like 1, 2, 3, 4), the tree becomes a single long chain, degrading performance to O(n). To guarantee O(log n) performance, the tree must stay balanced using rotations (like an AVL or Red-Black Tree).

Empty Tree. Insert a value.

How it works (Search)

def search(root, target):
    if not root:
        return False
        
    if root.val == target:
        return True
    elif target < root.val:
        return search(root.left, target)
    else:
        return search(root.right, target)