Understanding BST Properties: Advanced Optimization

struct TreeNode {
    int val;          // 4 bytes
    TreeNode* left;   // 8 bytes (64-bit pointer)
    TreeNode* right;  // 8 bytes (64-bit pointer)
};
// Total: 20 bytes, padded to 24 bytes by the compiler

Each node occupies 24 bytes (with alignment padding). A tree with 1 million nodes uses roughly 24 MB just for the nodes themselves — not counting the overhead of the heap allocator.

How Rotations Work

When an insert or delete violates the balance condition, the tree fixes itself using rotations. There are four rotation cases:

1. Left-Left (Right Rotation): The left child of the left child is too heavy. Rotate the unbalanced node rightward.
2. Right-Right (Left Rotation): The right child of the right child is too heavy. Rotate the unbalanced node leftward.
3. Left-Right (LR Rotation): Left child is heavy, but the imbalance is in its right subtree. First left-rotate the child, then right-rotate the node.
4. Right-Left (RL Rotation): Mirror of LR. First right-rotate the child, then left-rotate the node.

def right_rotate(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    return x

def left_rotate(x):
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    return y

Each rotation is O(1) — it simply reassigns three pointers. After insertion, at most one rotation (single or double) is needed per level, so rebalancing after insert is O(log n). The same applies to deletion, though deletion may require O(log n) rotations in the worst case.

O(log n) Kth Smallest with Subtree Sizes

def kth_smallest_augmented(root, k):
    node = root
    while node:
        left_size = node.left.size if node.left else 0
        if k == left_size + 1:
            return node.val
        elif k <= left_size:
            node = node.left
        else:
            k -= (left_size + 1)
            node = node.right
    return None

At each node, we check how many nodes are in the left subtree. If that count plus one equals k, we found the answer. If k is smaller, we go left. If k is larger, we subtract the left subtree size plus one and go right. This walks a single path from root to leaf — O(log n) on a balanced tree.

Finding the Rank of a Value

def find_rank(root, val):
    rank = 1
    node = root
    while node:
        if val < node.val:
            node = node.left
        elif val > node.val:
            left_size = node.left.size if node.left else 0
            rank += left_size + 1
            node = node.right
        else:
            left_size = node.left.size if node.left else 0
            return rank + left_size
    return -1  # Value not found

To find the rank of a value, we traverse from root to the target. Every time we go right, we add the size of the left subtree plus one (for the current node) to our running rank. This is also O(log n) on a balanced tree.

C++ std::map and std::set

The C++ Standard Library implements std::map, std::set, std::multimap, and std::multiset as Red-Black trees. They guarantee O(log n) insert, delete, and lookup. The lower_bound() and upper_bound() methods leverage the BST property to find ranges in O(log n).

Java TreeMap and TreeSet

Java's TreeMap and TreeSet are also backed by Red-Black trees. They provide ceilingKey(), floorKey(), subMap(), and headMap() — all implemented via BST traversal.

Database Indexes (B+ Trees)

Most relational databases (PostgreSQL, MySQL InnoDB) use B+ trees for indexes. While not binary trees, B+ trees are a generalization of BSTs optimized for disk I/O. Each internal node contains multiple keys and pointers, dramatically reducing tree height and minimizing expensive disk seeks. The fundamental BST property — ordered keys enabling binary search within each node — remains the same.

Linux Kernel

The Linux kernel uses Red-Black trees for process scheduling (CFS scheduler), virtual memory management, and file descriptor tracking. The rbtree implementation in include/linux/rbtree.h is one of the most battle-tested BST implementations in existence.