Binary Search Trees

A binary search tree (BST) is a binary tree with an ordering invariant:

left subtree values < node value < right subtree values

This invariant is what makes search efficient. At each node, one comparison decides whether the target can only be in the left subtree, only in the right subtree, or has been found.

The BST is best understood as an ordered dictionary structure. It supports membership tests, insertion, deletion, sorted traversal, predecessor/successor queries, and range queries. A hash table can often beat a BST for exact lookup, but a hash table cannot naturally answer “what is the next larger key?” or “print all keys between 20 and 50 in sorted order.”

Node Layout

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

typedef struct BSTNode {
    int value;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;

BSTNode *bst_node_new(int value) {
    BSTNode *node = malloc(sizeof(BSTNode));
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Search

BSTNode *bst_search(BSTNode *root, int target) {
    if (root == NULL || root->value == target) return root;
    if (target < root->value) return bst_search(root->left, target);
    return bst_search(root->right, target);
}

If the tree is balanced, search is O(log n). If the tree is skewed, search becomes O(n).

An iterative version avoids recursive call overhead:

BSTNode *bst_search_iter(BSTNode *root, int target) {
    while (root != NULL && root->value != target) {
        if (target < root->value) root = root->left;
        else root = root->right;
    }
    return root;
}

Insertion

Insertion follows the same path search would follow, then attaches the new node where the search falls off the tree.

BSTNode *bst_insert(BSTNode *root, int value) {
    if (root == NULL) return bst_node_new(value);

    if (value < root->value) {
        root->left = bst_insert(root->left, value);
    } else if (value > root->value) {
        root->right = bst_insert(root->right, value);
    }
    return root; /* duplicate values ignored */
}

The BST invariant must hold after every insertion. If values are inserted in sorted order, a plain BST degenerates into a linked list.

Insert 1, 2, 3, 4:

1
 \
  2
   \
    3
     \
      4

Duplicate Keys

Textbook BSTs often ignore duplicates, but real data may contain them. Common policies are:

• reject duplicates
• store a count field in each node
• place duplicates consistently on one side
• store a list of records for each key

Whatever policy is chosen must be part of the invariant. Inconsistent duplicate handling breaks search and deletion.

Traversal

Inorder traversal of a BST prints values in sorted order:

void bst_inorder(const BSTNode *root) {
    if (root == NULL) return;
    bst_inorder(root->left);
    printf("%d ", root->value);
    bst_inorder(root->right);
}

This works because the BST invariant guarantees that every left-subtree value comes before the node, and every right-subtree value comes after it.

Ordered Neighbors

The minimum value is the leftmost node. The maximum value is the rightmost node.

BSTNode *bst_max(BSTNode *root) {
    while (root != NULL && root->right != NULL) root = root->right;
    return root;
}

The successor of a value is the next larger value. If the node has a right subtree, the successor is the minimum of that right subtree. Otherwise, it is the deepest ancestor for which the node lies in the left subtree.

BSTNode *bst_successor(BSTNode *root, int value) {
    BSTNode *succ = NULL;
    while (root != NULL) {
        if (value < root->value) {
            succ = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return succ;
}

Predecessor is symmetric: move right when the current value is less than the target, remembering the last smaller candidate.

Deletion

Deleting a node has three cases:

1. Leaf: remove it and return NULL.
2. One child: replace the node with its only child.
3. Two children: replace the node’s value with its inorder successor, then delete the successor.

The inorder successor is the smallest value in the right subtree.

static BSTNode *bst_min(BSTNode *root) {
    while (root->left != NULL) root = root->left;
    return root;
}

BSTNode *bst_delete(BSTNode *root, int value) {
    if (root == NULL) return NULL;

    if (value < root->value) {
        root->left = bst_delete(root->left, value);
    } else if (value > root->value) {
        root->right = bst_delete(root->right, value);
    } else {
        if (root->left == NULL) {
            BSTNode *right = root->right;
            free(root);
            return right;
        }
        if (root->right == NULL) {
            BSTNode *left = root->left;
            free(root);
            return left;
        }

        BSTNode *successor = bst_min(root->right);
        root->value = successor->value;
        root->right = bst_delete(root->right, successor->value);
    }
    return root;
}

The two-child case is the one students should trace carefully. The successor is copied into the deleted node’s position because it is the next larger value, so the ordering invariant remains valid.

Range Queries

BSTs can skip entire subtrees during ordered queries.

void bst_print_range(const BSTNode *root, int lo, int hi) {
    if (root == NULL) return;
    if (root->value > lo) bst_print_range(root->left, lo, hi);
    if (root->value >= lo && root->value <= hi) printf("%d ", root->value);
    if (root->value < hi) bst_print_range(root->right, lo, hi);
}

In a balanced tree, range reporting costs O(log n + k), where k is the number of reported values.

Balanced BSTs

A plain BST gives O(log n) operations only when its height is O(log n). Self-balancing trees maintain that height automatically.

• AVL trees keep each node’s left and right subtree heights within 1.
• Red-black trees use coloring rules that keep the tree height bounded.

Both designs use rotations: local pointer rewiring that preserves inorder ordering while reducing height.

Rotations

A rotation changes shape without changing sorted order.

Right rotation:

      y              x
     / \            / \
    x   C   ->     A   y
   / \                / \
  A   B              B   C

The inorder sequence before and after is A, x, B, y, C. Because that sequence is unchanged, the BST invariant is preserved. AVL and red-black trees use rotations to keep height logarithmic after updates.

Pitfalls

• Treating a plain BST as guaranteed O(log n)
• Breaking the invariant during deletion
• Forgetting to return the new subtree root after insertion or deletion
• Mishandling duplicates
• Assuming preorder or postorder traversal is sorted
• Replacing a two-child node with an arbitrary descendant instead of predecessor/successor

Costs

Exercises

1. Insert {10, 5, 15, 3, 7, 12, 18} and draw the tree after every insertion.
2. Delete 10, identify the inorder successor, and draw the final tree.
3. Insert sorted values {1, 2, 3, 4, 5} and explain why the height becomes n - 1.
4. Explain why inorder traversal prints a BST in sorted order.