Binary search trees

Introduction

A binary search tree (BST) is a binary tree with one rule at every node: keys in the left subtree are smaller, keys in the right subtree are larger. So a search can throw away half of the tree at each step, like binary search in a sorted array, but inserting needs no shifting.

Sorted arrays search quickly but insert slowly, and linked lists do the opposite. A binary search tree aims to have both: it keeps keys in order and can add a new one without shifting anything.

How it works

Deleting a key

#include <stdio.h>
#include <stdlib.h>

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

Tree *insert(Tree *t, int key) {
    if (t == NULL) {
        Tree *n = malloc(sizeof(Tree));
        n->key = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key < t->key) t->left = insert(t->left, key);
    else if (key > t->key) t->right = insert(t->right, key);
    return t;
}

Tree *erase(Tree *t, int key) {
    if (t == NULL) return NULL;
    if (key < t->key) {
        t->left = erase(t->left, key);
    } else if (key > t->key) {
        t->right = erase(t->right, key);
    } else if (t->left == NULL || t->right == NULL) {   // no child or one child
        Tree *child = t->left != NULL ? t->left : t->right;
        free(t);
        return child;
    } else {                                            // two children
        Tree *next = t->right;
        while (next->left != NULL) next = next->left;   // the inorder successor
        t->key = next->key;
        t->right = erase(t->right, next->key);
    }
    return t;
}

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

int main(void) {
    int keys[] = {50, 30, 70, 20, 40, 60, 80};
    Tree *root = NULL;
    for (int i = 0; i < 7; i++) root = insert(root, keys[i]);
    root = erase(root, 20);   // a leaf
    root = erase(root, 30);   // one child
    root = erase(root, 50);   // two children: the root itself
    inorder(root);
    printf("\nroot is now %d\n", root->key);
    return 0;
}

Deleting has three cases:

1. A leaf (no children): remove it; the parent's pointer becomes NULL.
2. One child: the child takes the node's place.
3. Two children: copy in the inorder successor, the smallest key of the right subtree, then delete that key from the right subtree. The successor has no left child, so that second delete is case 1 or 2.

The code handles cases 1 and 2 together: child is whichever child exists, or NULL.

How fast?

Every operation walks one path from the root, so it costs O(h), where h is the tree's height. A balanced tree with n keys has height about log₂ n: a million keys, about 20 steps. But inserting keys that are already sorted (10, 20, 30, ...) makes every node a right child, a tree that is really a linked list, and the cost becomes O(n). Self-balancing trees (AVL, red-black) rotate nodes to prevent that.

Syntax

Tree *insert(Tree *t, int key) {
    if (t == NULL) return new_node(key);
    if (key < t->key) t->left = insert(t->left, key);
    else if (key > t->key) t->right = insert(t->right, key);
    return t;
}

Example

#include <stdio.h>
#include <stdlib.h>

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

Tree *insert(Tree *t, int key) {
    if (t == NULL) {
        Tree *n = malloc(sizeof(Tree));
        n->key = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key < t->key) t->left = insert(t->left, key);
    else if (key > t->key) t->right = insert(t->right, key);
    return t;   // a key that is already there is ignored
}

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

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

int main(void) {
    int keys[] = {50, 30, 70, 20, 40, 60};
    Tree *root = NULL;
    for (int i = 0; i < 6; i++) root = insert(root, keys[i]);
    inorder(root);
    printf("\n40 found: %d, 65 found: %d\n", contains(root, 40), contains(root, 65));
    return 0;
}

• Search: start at the root. Equal: found. Smaller: go left. Larger: go right. Reaching NULL means the key is not there.
• Insert: search for the key; where the search falls off the tree at NULL, hang a new node. insert returns the subtree's root, so the parent's left or right pointer is set as the recursion returns.

An inorder traversal of a BST visits the keys in sorted order: everything smaller, then the node, then everything larger.

Line by line

1. insert makes a new node when it reaches an empty place, and returns it.
2. Otherwise it recurses to the correct side and stores the returned pointer in t->left or t->right.
3. A key equal to t->key matches neither test, so duplicates are ignored.
4. contains uses a loop instead of recursion: it moves left or right until it finds the key or reaches NULL.
5. inorder prints the keys in sorted order.
6. main inserts six keys, prints them, then reports that 40 is present and 65 is not.

Expected result

20 30 40 50 60 70 
40 found: 1, 65 found: 0

In the real world

Language libraries offer sorted maps built on balanced search trees, such as C++'s std::map. Whenever a program must look things up by key and also list them in order, a search tree is the usual answer.

Common mistakes

• Writing insert(t->left, value); without t->left = ...: the new node is created and lost.
• In the two-children case, deleting the original key instead of the successor's copy.
• Assuming a BST is always fast: sorted input gives the worst case.

Best practices

• Always store the pointer that insert or delete returns.
• Check the inorder output after every change while testing.
• Use a balanced tree when the input may arrive already sorted.

Summary

A binary search tree keeps smaller keys on the left and larger keys on the right, so operations walk a single path. They cost O(height), which is about log n when the tree is balanced and n when it is not.

Mark lesson complete