Binary search trees

Why this matters

A hash table finds a key in O(1), but it keeps keys in no useful order: you cannot ask it for "all names between Adams and Baker" or "the smallest timestamp after 10:00". A binary search tree keeps keys sorted at all times while still supporting fast insertion, lookup and deletion, typically O(log n). Balanced variants of it sit inside database indexes, file systems, the Linux kernel's scheduler and memory manager (red-black trees), and the ordered maps of C++ and Java. Trees are also the natural home of recursion: almost every tree operation is three lines once you see the recursive shape.

Trees, briefly

A binary tree is made of nodes, each with up to two children, left and right. The top node is the root; nodes without children are leaves. Each child is itself the root of a smaller tree, a subtree, which is why recursive code fits so well.

typedef struct Tree {
    int key;
    struct Tree *left, *right;
} Tree;

Just like a linked list, a tree is a collection of separately allocated nodes connected by pointers, and the whole tree is represented by a pointer to its root (NULL for an empty tree).

The BST property

A binary search tree adds one rule, for every node: all keys in its left subtree are smaller than its key, and all keys in its right subtree are larger.

  inserting 50, 30, 70, 20, 40, 60, 80:

              50                 everything left of 50 is < 50
            /    \               everything right of 50 is > 50
          30      70
         /  \    /  \
        20  40  60  80

To search, start at the root and compare: smaller goes left, larger goes right, equal means found, NULL means absent. Each step discards an entire subtree, so in a well-shaped tree with a million keys a search takes about 20 comparisons (2^20 is about a million). That is binary search, but on a structure you can insert into without shifting an array.

The operations

/* Insert key, ignoring duplicates. Returns the (possibly new) root. */
Tree *insert(Tree *root, int key)
{
    if (root == NULL) {
        Tree *n = malloc(sizeof *n);
        if (n == NULL)
            return NULL;
        n->key = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key < root->key)
        root->left = insert(root->left, key);
    else if (key > root->key)
        root->right = insert(root->right, key);
    return root;
}

int contains(const Tree *t, int key)
{
    while (t != NULL) {
        if (key == t->key)
            return 1;
        t = key < t->key ? t->left : t->right;
    }
    return 0;
}

insert says: inserting into an empty tree produces a one-node tree; otherwise, insert into the correct subtree and store whatever comes back as that child. The assignment root->left = insert(root->left, key) is what links a new node into place: when the recursion reaches the NULL child, it returns the new node, and the caller stores it. Returning the root also lets main handle the first insertion, when root is NULL, with no special case (the same problem the Node ** technique solved for lists).

contains needs no recursion at all: it follows one path down, so a loop is simplest.

Traversals

Visiting every node has three classic recursive orders, named by when the node itself is handled:

void print_inorder(const Tree *t)        /* left, node, right */
{
    if (t == NULL)
        return;
    print_inorder(t->left);
    printf("%d ", t->key);
    print_inorder(t->right);
}

• In-order (left, node, right) visits a BST's keys in sorted order: everything smaller, then the node, then everything larger.
• Pre-order (node, left, right) visits a parent before its children: useful for copying a tree or printing it as an outline.
• Post-order (left, right, node) visits children before their parent: exactly the order needed to free a tree, since freeing a parent first would lose the pointers to its children.

void free_tree(Tree *t)
{
    if (t == NULL)
        return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

int height(const Tree *t)
{
    if (t == NULL)
        return 0;
    int l = height(t->left), r = height(t->right);
    return 1 + (l > r ? l : r);
}

Putting them together:

int main(void)
{
    int keys[] = {50, 30, 70, 20, 40, 60, 80, 30};
    Tree *root = NULL;
    for (int i = 0; i < 8; i++)
        root = insert(root, keys[i]);
    print_inorder(root);
    printf("\nheight %d, contains 60: %d, contains 65: %d\n",
           height(root), contains(root, 60), contains(root, 65));
    free_tree(root);

    root = NULL;
    for (int i = 1; i <= 7; i++)
        root = insert(root, i * 10);
    printf("sorted input -> height %d\n", height(root));
    free_tree(root);
    return 0;
}

20 30 40 50 60 70 80
height 3, contains 60: 1, contains 65: 0
sorted input -> height 7

The duplicate 30 was ignored, and valgrind confirms all nodes were freed.

Recursion and the call stack

Each recursive call gets its own stack frame holding its own t, as you saw in the functions module. The depth of recursion equals the height of the tree. For a balanced tree of a million keys that is about 20 frames, nothing at all. But see the last line of the output above.

The weak spot: degenerate trees

Inserting keys in sorted order builds a tree where every node has only a right child:

  10
    \
     20
       \
        30          height 7 for 7 nodes:
          \         a linked list wearing a tree costume
           ...

Search, insert and height all become O(n), and recursive functions recurse n levels deep: a tree built from a million sorted keys would overflow the stack in the recursive insert. Sorted input is not exotic; it is what you get from timestamps, IDs and already-sorted files.

The real-world fix is a self-balancing tree, which restructures itself with small local "rotations" during insertion so its height stays O(log n) whatever the input order. The common ones are AVL trees and red-black trees; the Linux kernel's rbtree.h and C++'s std::map are red-black trees. They are beyond this lesson, but the BST you wrote is their foundation: they are BSTs with extra bookkeeping.

Deleting, in one paragraph

Removing a key has three cases: a leaf is simply freed (and its parent's pointer set to NULL); a node with one child is replaced by that child; a node with two children takes the key of its in-order successor (the smallest key in its right subtree), and that successor node, which has at most one child, is deleted instead. Try it as an exercise after this lesson.

Common mistakes

• Not storing the result of the recursive insert: insert(root->left, key); alone allocates a node and leaks it, leaving the tree unchanged.
• Freeing in pre-order, then reading t->left from freed memory.
• Checking the BST property only between parent and child. The property is about entire subtrees; a key deep in the left subtree can still be too large.
• Forgetting the empty tree. Every recursive function needs the t == NULL base case.
• Assuming O(log n). Only balanced trees guarantee it; a plain BST fed sorted data is O(n) per operation and can blow the stack.

Recap

• A BST keeps smaller keys in the left subtree and larger in the right, at every node.
• Search follows one path; insert recurses and links the new node in via the returned pointer.
• In-order traversal yields sorted keys; post-order is the order for freeing.
• Height decides cost: about log2(n) when balanced, n when degenerate (sorted input).
• Self-balancing trees (AVL, red-black) keep the height logarithmic.

Going further: implement delete_key with the three cases above and test it under valgrind with random insertions and deletions, checking is_bst after every step. Then read the comments at the top of the Linux kernel's lib/rbtree.c for a description of red-black tree rules.