Binary Search Trees

Updated

October 31, 2026

Binary Search Trees

A Binary Search Tree (BST) arranges key-value pairs hierarchically such that every left subtree key is smaller than its root, and every right subtree key is greater. While Python’s built-in dict provides amortized \(O(1)\) key lookups, a BST provides sorted traversals, range scans, and minimum/maximum finding in \(O(h)\) time, where \(h\) is tree height.

Binary Search Tree Diagram

Mental model

In a balanced BST containing \(n\) elements, the height \(h \approx \log_2 n\). Locating or inserting an element discards half the remaining tree at each node decision:

            [ 50: Central ]
            /             \
     [ 25: North ]       [ 75: South ]
      /         \
[ 15: East ]   [ 35: West ]
  • Search Path for 35: Root is \(50 \implies 35 < 50\) (Go Left to \(25\)). \(35 > 25\) (Go Right to \(35 \implies\) Found!).
  • In-Order Traversal: Recursively visiting Left -> Node -> Right yields keys in strictly sorted ascending order (15, 25, 35, 50, 75).
  • Deletion:
    • Leaf Node: Simply disconnect from parent.
    • One Child: Connect parent directly to the single child.
    • Two Children: Replace node key with its in-order successor (the minimum node in the right subtree), then delete the successor from the right subtree.

Worked examples

Case 1: Generic BST with Insert, Search, and In-Order Generator

Save as bst_desk.py. Implement a BST with type annotations and a generator for memory-efficient sorted iteration.

# bst_desk.py
from collections.abc import Iterator


class BSTNode[K, V]:
    __slots__ = ("key", "val", "left", "right")

    def __init__(self, key: K, val: V) -> None:
        self.key: K = key
        self.val: V = val
        self.left: BSTNode[K, V] | None = None
        self.right: BSTNode[K, V] | None = None


class BinarySearchTree[K, V]:
    def __init__(self) -> None:
        self.root: BSTNode[K, V] | None = None
        self._size = 0

    def insert(self, key: K, val: V) -> None:
        self.root = self._insert_node(self.root, key, val)

    def _insert_node(
        self, node: BSTNode[K, V] | None, key: K, val: V
    ) -> BSTNode[K, V]:
        if node is None:
            self._size += 1
            return BSTNode(key, val)

        if key < node.key:
            node.left = self._insert_node(node.left, key, val)
        elif key > node.key:
            node.right = self._insert_node(node.right, key, val)
        else:
            node.val = val  # Update value for existing key
        return node

    def search(self, key: K) -> V | None:
        curr = self.root
        while curr is not None:
            if key == curr.key:
                return curr.val
            elif key < curr.key:
                curr = curr.left
            else:
                curr = curr.right
        return None

    def in_order(self) -> Iterator[tuple[K, V]]:
        def _walk(node: BSTNode[K, V] | None) -> Iterator[tuple[K, V]]:
            if node is not None:
                yield from _walk(node.left)
                yield (node.key, node.val)
                yield from _walk(node.right)

        yield from _walk(self.root)


def main() -> None:
    tree: BinarySearchTree[int, str] = BinarySearchTree()
    tree.insert(50, "Depot Central")
    tree.insert(25, "Depot North")
    tree.insert(75, "Depot South")
    tree.insert(15, "Substation East")
    tree.insert(35, "Substation West")

    # Search
    target = 35
    result = tree.search(target)
    print(f"Search for ID {target}: {result}")

    # Sorted walkthrough
    print("\nIn-order sorted sequence:")
    for key, val in tree.in_order():
        print(f"  ID {key} -> {val}")


if __name__ == "__main__":
    main()

Run:

uv run python bst_desk.py

Output:

Search for ID 35: Substation West

In-order sorted sequence:
  ID 15 -> Substation East
  ID 25 -> Depot North
  ID 35 -> Substation West
  ID 50 -> Depot Central
  ID 75 -> Depot South

Case 2: Deleting Nodes (Handling 0, 1, and 2 Children)

Save as bst_deletion.py. Demonstrate deleting nodes across all three structural conditions.

# bst_deletion.py
from dataclasses import dataclass


@dataclass
class Node:
    key: int
    left: "Node | None" = None
    right: "Node | None" = None


def insert(root: Node | None, key: int) -> Node:
    if root is None:
        return Node(key=key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root


def find_min(node: Node) -> Node:
    curr = node
    while curr.left is not None:
        curr = curr.left
    return curr


def delete_node(root: Node | None, key: int) -> Node | None:
    if root is None:
        return None

    if key < root.key:
        root.left = delete_node(root.left, key)
    elif key > root.key:
        root.right = delete_node(root.right, key)
    else:
        # Node found

        # Case 1 & 2: 0 or 1 child
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left

        # Case 3: 2 children -> replace with in-order successor
        successor = find_min(root.right)
        root.key = successor.key
        root.right = delete_node(root.right, successor.key)

    return root


def to_sorted_list(root: Node | None) -> list[int]:
    if root is None:
        return []
    return to_sorted_list(root.left) + [root.key] + to_sorted_list(root.right)


def main() -> None:
    root: Node | None = None
    for k in [50, 30, 70, 20, 40, 60, 80]:
        root = insert(root, k)

    print("Initial tree:", to_sorted_list(root))

    print("Deleting leaf node 20 (0 children)...")
    root = delete_node(root, 20)
    print("Tree:", to_sorted_list(root))

    print("Deleting node 30 (1 child: 40)...")
    root = delete_node(root, 30)
    print("Tree:", to_sorted_list(root))

    print("Deleting root 50 (2 children: replaced by successor 60)...")
    root = delete_node(root, 50)
    print("Tree:", to_sorted_list(root))


if __name__ == "__main__":
    main()

Run:

uv run python bst_deletion.py

Output:

Initial tree: [20, 30, 40, 50, 60, 70, 80]
Deleting leaf node 20 (0 children)...
Tree: [30, 40, 50, 60, 70, 80]
Deleting node 30 (1 child: 40)...
Tree: [40, 50, 60, 70, 80]
Deleting root 50 (2 children: replaced by successor 60)...
Tree: [40, 60, 70, 80]

The trap

The trap in unbalanced binary search trees is Python’s default recursion limit (sys.getrecursionlimit(), typically 1,000). When data is inserted in sorted order (1, 2, 3, ...), the tree becomes a single linked list of depth \(n\). Inserting or searching for the 1,001st element raises RecursionError: maximum recursion depth exceeded.

For production trees, write iterative while loops for searches, or use balanced search trees (AVL or Red-Black).

The boring rule

  1. Use standard Python dict when you only need \(O(1)\) exact-key lookups.
  2. Use a BST or bisect when you need sorted traversal, minimum/maximum queries, or range queries (min_key <= k <= max_key).
  3. Prefer iterative loops over deep recursion for search() to avoid hitting Python’s recursion limit.
  4. If keys arrive in sorted order, shuffle them with random.shuffle() before tree construction if a self-balancing tree is unavailable.

Try this

  1. Implement range_query(min_k, max_k) on BinarySearchTree using an in-order generator that yields all items within the range without scanning outside subtrees.
  2. Add a height() function that computes the depth of the tree recursively.