Search Trees

A search tree stores values so that structural position encodes order. At each node, a comparison eliminates an entire region of the tree: smaller values belong on one side and larger values on the other. When height remains logarithmic, search, insertion, and deletion are logarithmic; when shape degenerates into a chain, those same operations become linear.

Search trees are valuable not only for exact membership. They preserve sorted order, making minimum, maximum, predecessor, successor, floor, ceiling, and range queries natural. A hash table usually cannot answer those ordered questions without additional structure.

Why Do We Need Search Trees?

Suppose a calendar application stores appointments by starting time. While the application is running, users may need to:

• add a new appointment;
• find an appointment at an exact time;
• cancel an appointment;
• show the earliest or latest appointment;
• find the next appointment after the current time;
• list every appointment between 09:00 and 12:00;
• display all appointments in chronological order.

Different basic structures solve only part of this problem well:

A search tree is useful when data changes over time and the program needs to preserve order. In a balanced tree, exact search, insertion, deletion, minimum/maximum, and neighboring-value queries can all be logarithmic.

An ordinary BST provides the ordering behavior but can become unbalanced. AVL and red-black trees later in this chapter add rules that guarantee logarithmic height.

Everyday Ordered Questions

Physical systems do not necessarily store a literal BST, but many everyday questions have the same ordered form:

• Appointment book: What is the next appointment after 10
  ?
• Dictionary: Which word comes immediately before or after another word alphabetically?
• Leaderboard: Which score is higher, and which players fall within a score range?
• Library catalogue: Which titles fall between two alphabetic boundaries?
• Reservation schedule: Is a time present, and what is the nearest available time before or after it?
• Price list: Which products fall between two prices?

These are not only “is this value present?” questions. They depend on relative order, neighbors, minimum/maximum values, or ranges.

Search Trees in Software

• Ordered sets and maps: many libraries provide containers that keep entries sorted while supporting dynamic insertion and deletion. Balanced search trees are a common implementation family.
• In-memory indexes: applications can index changing records by time, name, price, or another comparable field.
• Event and timer systems: events can be ordered by scheduled time so the earliest event and nearby time range are easy to find.
• Autocomplete and prefix ranges: lexicographically ordered strings with a shared prefix occupy a contiguous range. Tries may be better for some prefix-heavy workloads, but search trees can support the range operation.
• Leaderboards and ranking: a tree augmented with subtree sizes can find ranks and the kth entry while values change.
• Compilers and development tools: ordered symbol collections support deterministic sorted output and range-like queries, although hash tables are also common when only exact lookup matters.
• Memory management: allocators may keep free blocks ordered by address or size to find neighboring or sufficiently large blocks.
• Geometric and interval indexes: specialized search-tree variants organize coordinates, intervals, or regions for overlap and range queries.

Disk-based databases usually use B-trees or related multiway trees, not ordinary binary search trees. A disk page can hold many keys and child links, reducing expensive page reads. The underlying motivation—maintaining order for search and ranges—is related, but the representation is designed for storage hardware.

Matching Applications to Operations

Each application question leads naturally to one search-tree operation:

This mapping is why a search tree offers more than a single search function. The stored order supports a family of related questions.

When Is a Search Tree the Wrong Choice?

• Use a hash table when exact lookup dominates and sorted iteration or ranges are unnecessary.
• Use a sorted array when updates are rare and compact memory with fast binary search matters more than insertion cost.
• Use a heap when the program mainly needs repeated access to only the smallest or largest priority.
• Use a trie when operations are dominated by string prefixes and character-by-character lookup.
• Use a B-tree family for large disk- or page-oriented indexes.

The right question is not “Is a BST fast?” It is “Which operations must remain efficient, and does this implementation control its height?”

Ordered ADT

A search-tree set may offer:

insert(value)
remove(value)
contains(value)
minimum()
maximum()
predecessor(value)
successor(value)
floor(value)
ceiling(value)
range(low, high)
size()

A dictionary stores key-value entries rather than plain values. In that setting, the key is the field used for ordering and the value is the associated information. The introductory integer BST has no separate associated information, so its code simply calls the stored integer value.

The code in this chapter implements an integer set so structural reasoning stays visible. A generic dictionary needs a comparison function and an explicit value-ownership policy.

Binary Tree vs Binary Search Tree

Both structures give each node at most two children, but only a BST assigns meaning to value placement:

Calling a structure a BST therefore makes a stronger promise than calling it a binary tree. Every insertion and deletion must preserve that promise.

BST Invariant

For every node x in a binary search tree (BST):

every value in x's left subtree  < x.value
every value in x's right subtree > x.value
both subtrees satisfy the same rule recursively

The uneven tree used throughout the introductory implementation satisfies this rule:

                 50
               /    \
             30      70
            /  \       \
          20   40       90
              /        /
             35       80
            /
           33

The rule is global, not merely parent-to-child. Placing 45 beneath 70 would violate the invariant because every node in the right subtree of 50 must be greater than 50, even though 45 could still be smaller than its immediate parent.

Range interpretation

Each comparison narrows the valid interval:

root 50:          (-infinity, +infinity)
left child 30:    (-infinity, 50)
node 40:          (30, 50)
node 35:          (30, 40)
node 33:          (30, 35)
right child 70:   (50, +infinity)
node 90:          (70, +infinity)
node 80:          (70, 90)

This range view is the most reliable way to validate a BST. Checking only the immediate child values can miss deeper violations.

BST: Function-by-Function

The learner-friendly implementation stores only a pointer to the root. Each function receives that root and either returns a result or returns the updated root. This is the same visible style used for a singly linked list whose operations return an updated head.

Node Creation

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

The node shape is the same as an ordinary binary-tree node. The difference is the ordering rule imposed on the values.

BSTNode *createBSTNode(int value) {
    BSTNode *newNode = malloc(sizeof(BSTNode));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

The introductory version stops if allocation fails so the remaining functions can focus on the BST algorithm.

Root Return

Insertion and deletion may change the root of a subtree. Returning that root keeps the change visible:

root = insertNode(root, 50);
root = deleteNode(root, 50);

The same rule applies inside a function:

root->left = insertNode(root->left, value);

The recursive call returns the possibly changed left-subtree root, and the assignment reconnects it to its parent.

For the first insertion, root is NULL, so insertNode(NULL, 50) creates and returns node 50. The caller must keep that returned pointer:

BSTNode *root = NULL;
root = insertNode(root, 50);

Without the assignment, the allocated node would not become the tree’s root.

Insert

Insertion follows the ordering rule until it reaches an empty position:

BSTNode *insertNode(BSTNode *root, int value) {
    if (root == NULL) {
        return createBSTNode(value);
    }

    if (value < root->value) {
        root->left = insertNode(root->left, value);
    } else if (value > root->value) {
        root->right = insertNode(root->right, value);
    }

    return root;
}

There are three decisions:

• an empty position creates the new leaf;
• a smaller value continues into the left subtree;
• a larger value continues into the right subtree.

If the value equals root->value, neither branch runs. This version therefore ignores duplicates.

Insertion Trace

After inserting the first eight example values, insert 33:

The null position becomes the new leaf:

    35
   /
  33

The recursive calls then return in reverse order:

return 33 to the call at 35  -> 35->left remains 33
return 35 to the call at 40  -> 40->left remains 35
return 40 to the call at 30  -> 30->right remains 40
return 30 to the call at 50  -> 50->left remains 30

Most returns give back the same subtree root they received. They still matter because insertion into an empty subtree returns a new root that its parent must connect.

Insert these values in order:

50, 30, 70, 20, 40, 90, 35, 80, 33

They produce an uneven BST:

                 50
               /    \
             30      70
            /  \       \
          20   40       90
              /        /
             35       80
            /
           33

The deepest path through the root’s left subtree has four edges: 50 -> 30 -> 40 -> 35 -> 33. The deepest path through its right subtree has three: 50 -> 70 -> 90 -> 80. The BST rule does not guarantee equal subtree heights.

Search

Search makes the same comparison as insertion but does not create a node:

BSTNode *searchNode(BSTNode *root, int targetValue) {
    if (root == NULL || root->value == targetValue) {
        return root;
    }

    if (targetValue < root->value) {
        return searchNode(root->left, targetValue);
    }
    return searchNode(root->right, targetValue);
}

Searching for 33 follows this path:

33 < 50  -> left
33 > 30  -> right
33 < 40  -> left
33 < 35  -> left
33 == 33 -> found

Every comparison rejects one complete subtree. Search takes Theta(h) time, where h is the tree height.

A missing value follows comparisons in exactly the same way. Searching for 34 reaches:

50 -> 30 -> 40 -> 35 -> 33 -> right NULL

Reaching NULL means the only position where 34 could occur is empty, so the function returns NULL. It does not need to inspect nodes 20, 70, 80, or 90.

Change the insertion order and target below to see how tree shape changes the search path.

BST Traversals

A BST supports the same preorder, inorder, postorder, and level-order traversals as any binary tree. Its special traversal is inorder because the ordering invariant makes the output sorted.

void inorderTraversal(BSTNode *root) {
    if (root == NULL) {
        return;
    }

    inorderTraversal(root->left);
    printf("%d ", root->value);
    inorderTraversal(root->right);
}

For the uneven BST:

Notice that only inorder is sorted. Preorder exposes the root-first insertion shape, postorder finishes descendants before parents, and level order exposes depth.

The sorted result is not an accidental property of this example. At every node, inorder performs:

all smaller values -> current value -> all larger values

For subtree 40, it prints 33 35 40; for subtree 30, it combines 20, 30, and that sorted right-subtree result to produce 20 30 33 35 40.

Count Nodes

Counting nodes does not use the BST ordering rule; both subtrees must be counted:

int countNodes(BSTNode *root) {
    if (root == NULL) {
        return 0;
    }

    return 1 + countNodes(root->left)
             + countNodes(root->right);
}

The uneven example contains nine nodes. A larger implementation may maintain a size field for constant-time access, but then every successful insertion and deletion must update it correctly.

Find Height

Height follows the deeper subtree:

int calculateHeight(BSTNode *root) {
    if (root == NULL) {
        return -1;
    }

    int leftHeight = calculateHeight(root->left);
    int rightHeight = calculateHeight(root->right);

    if (leftHeight > rightHeight) {
        return 1 + leftHeight;
    }
    return 1 + rightHeight;
}

The example’s left subtree is one level deeper, so the complete BST has height 4. Ordinary BST operations follow one path and may therefore become slow when one side grows much deeper than the other.

The root calculation makes the unequal depths explicit:

height(subtree rooted at 30) = 3
height(subtree rooted at 70) = 2
height(tree rooted at 50)    = 1 + max(3, 2) = 4

Insertion and search for 33 follow the longer side and require more comparisons than operations near the root.

Find Minimum and Maximum

The smallest value is found by following left links until no further left child exists:

BSTNode *findMinimum(BSTNode *root) {
    if (root == NULL) {
        return NULL;
    }

    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

The maximum is symmetric and follows right links:

BSTNode *findMaximum(BSTNode *root) {
    if (root == NULL) {
        return NULL;
    }

    while (root->right != NULL) {
        root = root->right;
    }
    return root;
}

In the example, 20 is the minimum and 90 is the maximum. Neither value needs to be a leaf in every possible BST; the minimum only needs to have no left child, and the maximum only needs to have no right child.

The actual paths are short:

minimum: 50 -> 30 -> 20
maximum: 50 -> 70 -> 90

The functions follow only one path, so each takes Theta(h) time rather than traversing all n nodes.

BST Deletion: Function-by-Function

Deletion first searches for the target value. After finding it, the number of children determines what happens.

Case 1: Delete a Leaf

A leaf has no children, so it can be freed and replaced by NULL:

    30                 30
   /         ->
  20

The return value tells the parent that this child position is now empty.

In the example, deleting 20 changes 30->left from the address of node 20 to NULL.

Case 2: Delete a Node with One Child

The only child moves into the deleted node’s position:

     35                33
    /         ->
   33

The node is freed, but its child subtree is preserved and returned to the parent.

In the example, deleting 35 returns its left child 33. The assignment performed by the caller changes 40->left from node 35 to node 33.

Case 3: Delete a Node with Two Children

Neither child can simply be discarded. This implementation copies the inorder successor—the smallest value in the right subtree—into the target node, then deletes the old successor node.

Before deleting 50:             After deleting 50:

        50                              70
      /    \                          /    \
    30      70                       30      90
              \                             /
               90                          80
              /
             80

Only part of each tree is shown. All nodes in the left subtree remain smaller than the replacement value, and all remaining nodes in the right subtree remain larger.

Deleting 50 has two separate stages:

1. findMinimum(root->right) selects 70, the smallest value greater than 50.
2. The root value becomes 70, then the old node containing 70 is deleted from the right subtree.

Copying without the second stage would leave two nodes containing 70.

Complete Delete Function

BSTNode *deleteNode(BSTNode *root, int targetValue) {
    if (root == NULL) {
        return NULL;
    }

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

        if (root->right == NULL) {
            BSTNode *replacementChild = root->left;
            free(root);
            return replacementChild;
        }

        BSTNode *successor = findMinimum(root->right);
        root->value = successor->value;
        root->right = deleteNode(root->right, successor->value);
    }

    return root;
}

The first comparisons locate the target value. Inside the matching case:

• no left child means the right child, possibly NULL, replaces the node;
• no right child means the left child replaces the node;
• two children use the inorder successor and reduce the second deletion to an easier case.

Always assign the returned pointer:

root = deleteNode(root, 50);

Ignoring the return value fails when the root itself is replaced.

If the target is absent, recursion eventually receives NULL and returns NULL to the existing null child field. All earlier calls reconnect the same subtree roots, so the tree remains unchanged.

Free the BST

void freeBST(BSTNode *root) {
    if (root == NULL) {
        return;
    }

    freeBST(root->left);
    freeBST(root->right);
    free(root);
}

Cleanup uses postorder so a parent remains valid until both child subtrees have been released.

Common Beginner Mistakes

Comparing Only with the Parent

A node must satisfy every ancestor range, not only its immediate parent. A value 45 cannot appear anywhere in the right subtree of 50, even if it is smaller than a local parent such as 70.

Ignoring a Returned Root

Use root = insertNode(root, value) and root = deleteNode(root, value). The same rule applies to root->left and root->right inside recursive functions.

Searching Both Subtrees

A BST comparison proves which subtree may contain the target. Searching both sides still works as a binary-tree traversal, but it throws away the BST’s main performance advantage.

Assuming Every BST Is Balanced

The ordering invariant controls value placement, not height. Sorted insertion can create a one-sided chain, making search, insertion, and deletion linear.

Forgetting the Second Deletion

In the two-child case, copying the successor value is only the first step. The original successor node must also be deleted or the tree will contain a duplicate.

BST: Full Code

This complete program uses short names and explicit insertions so each operation is easy to find. It builds the same uneven BST used in the explanations.

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

#define MAX_NODES 100

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node* createNode(int data) {
    struct Node* newNode = malloc(sizeof(struct Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

struct Node* insert(struct Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }

    return root;
}

struct Node* search(struct Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }

    if (data < root->data) {
        return search(root->left, data);
    }

    return search(root->right, data);
}

void inorder(struct Node* root) {
    if (root == NULL) {
        return;
    }

    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

void preorder(struct Node* root) {
    if (root == NULL) {
        return;
    }

    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

void postorder(struct Node* root) {
    if (root == NULL) {
        return;
    }

    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

void levelOrder(struct Node* root) {
    if (root == NULL) {
        return;
    }

    struct Node* queue[MAX_NODES];
    int front = 0;
    int rear = 0;

    queue[rear++] = root;

    while (front < rear) {
        struct Node* current = queue[front++];
        printf("%d ", current->data);

        if (current->left != NULL) {
            queue[rear++] = current->left;
        }
        if (current->right != NULL) {
            queue[rear++] = current->right;
        }
    }
}

struct Node* findMinimum(struct Node* root) {
    if (root == NULL) {
        return NULL;
    }

    while (root->left != NULL) {
        root = root->left;
    }

    return root;
}

struct Node* findMaximum(struct Node* root) {
    if (root == NULL) {
        return NULL;
    }

    while (root->right != NULL) {
        root = root->right;
    }

    return root;
}

int countNodes(struct Node* root) {
    if (root == NULL) {
        return 0;
    }

    return 1 + countNodes(root->left) + countNodes(root->right);
}

int height(struct Node* root) {
    if (root == NULL) {
        return -1;
    }

    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    if (leftHeight > rightHeight) {
        return leftHeight + 1;
    }

    return rightHeight + 1;
}

struct Node* deleteNode(struct Node* root, int data) {
    if (root == NULL) {
        return NULL;
    }

    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        // No left child: use the right child as the replacement.
        if (root->left == NULL) {
            struct Node* replacement = root->right;
            free(root);
            return replacement;
        }

        // No right child: use the left child as the replacement.
        if (root->right == NULL) {
            struct Node* replacement = root->left;
            free(root);
            return replacement;
        }

        // Two children: replace the data with the inorder successor.
        struct Node* successor = findMinimum(root->right);
        root->data = successor->data;
        root->right = deleteNode(root->right, successor->data);
    }

    return root;
}

void freeTree(struct Node* root) {
    if (root == NULL) {
        return;
    }

    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main(void) {
    struct Node* root = NULL;

    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 90);
    root = insert(root, 35);
    root = insert(root, 80);
    root = insert(root, 33);

    printf("Inorder: ");
    inorder(root);

    printf("\nPreorder: ");
    preorder(root);

    printf("\nPostorder: ");
    postorder(root);

    printf("\nLevel order: ");
    levelOrder(root);

    printf("\n\nSearching 33: ");
    if (search(root, 33) != NULL) {
        printf("Found");
    } else {
        printf("Not found");
    }

    printf("\nMinimum: %d", findMinimum(root)->data);
    printf("\nMaximum: %d", findMaximum(root)->data);
    printf("\nTotal nodes: %d", countNodes(root));
    printf("\nHeight: %d", height(root));

    root = deleteNode(root, 20);
    printf("\n\nAfter deleting 20 (leaf): ");
    inorder(root);

    root = deleteNode(root, 35);
    printf("\nAfter deleting 35 (one child): ");
    inorder(root);

    root = deleteNode(root, 50);
    printf("\nAfter deleting 50 (two children): ");
    inorder(root);

    printf("\n");
    freeTree(root);
    return 0;
}

Expected output:

Inorder: 20 30 33 35 40 50 70 80 90
Preorder: 50 30 20 40 35 33 70 90 80
Postorder: 20 33 35 40 30 80 90 70 50
Level order: 50 30 70 20 40 90 35 80 33

Searching 33: Found
Minimum: 20
Maximum: 90
Total nodes: 9
Height: 4

After deleting 20 (leaf): 30 33 35 40 50 70 80 90
After deleting 35 (one child): 30 33 40 50 70 80 90
After deleting 50 (two children): 30 33 40 70 80 90

The level-order function uses a fixed queue of MAX_NODES pointers for teaching. A reusable BST should use a growable or circular queue when its maximum node count is not known in advance.

Duplicate Policies

The simple insertNode function ignores duplicate values. Other valid policies include storing a count in each node or storing a collection for each distinct value. Whichever policy is chosen must be stated clearly and used consistently by insertion, deletion, traversal, and size calculations.

Ordered Queries

The BST order also supports predecessor, successor, floor, ceiling, and range queries.

Predecessor

The predecessor of targetValue is the greatest stored value smaller than targetValue:

BSTNode *findPredecessor(BSTNode *root, int targetValue) {
    BSTNode *candidate = NULL;

    while (root != NULL) {
        if (targetValue <= root->value) {
            root = root->left;
        } else {
            candidate = root;
            root = root->right;
        }
    }

    return candidate;
}

Moving right records a smaller value that may be the answer. Moving left searches for a closer smaller value without accepting the current, too-large node.

Successor, Floor, and Ceiling

The successor is the least stored value greater than a target value. Reverse the predecessor comparisons: moving left records a possible successor, while moving right discards a value that is too small.

The floor is the greatest stored value less than or equal to the target. The ceiling is the least stored value greater than or equal to it. If the exact value exists, it is its own floor and ceiling.

Range Query

An inorder traversal can skip subtrees that cannot contain values in [low, high]:

void printRange(BSTNode *root, int low, int high) {
    if (root == NULL) {
        return;
    }

    if (root->value > low) {
        printRange(root->left, low, high);
    }
    if (root->value >= low && root->value <= high) {
        printf("%d ", root->value);
    }
    if (root->value < high) {
        printRange(root->right, low, high);
    }
}

In a balanced tree this takes O(log n + k) for k printed values. An uneven, skewed tree may require O(n) time.

Tree Degeneration

Inserting already sorted values into an ordinary BST produces:

10
  \
   20
     \
      30
        \
         40

Its height is n - 1. Search, insertion, and deletion then take Theta(n), matching a linked list with comparisons.

For randomly ordered distinct values, expected height is logarithmic, but that is not a worst-case guarantee. Input may already be sorted or deliberately chosen to create poor shape. Balanced search trees maintain additional rules to guarantee logarithmic height.

Tree Rotations

A rotation changes local shape without changing inorder value order.

Right rotation

        y                         x
       / \                       / \
      x   C      rotate y       A   y
     / \         right             / \
    A   B                         B   C

The subtrees obey:

A < x < B < y < C

After rotation, that order remains true.

BSTNode *rotateRight(BSTNode *topNode) {
    BSTNode *leftChild = topNode->left;
    BSTNode *middleSubtree = leftChild->right;

    leftChild->right = topNode;
    topNode->left = middleSubtree;
    return leftChild;
}

The caller installs the returned root. In a metadata-bearing tree, refresh the lower node before the new root because the new root’s measurement depends on the lower node’s updated measurement.

Left rotation

Left rotation is the mirror image:

    x                              y
   / \                            / \
  A   y       rotate x           x   C
     / \       left             / \
    B   C                       A   B

Rotations are constant-time pointer transformations. They do not by themselves decide when rebalancing is needed.

AVL Trees

An AVL tree is a BST that stores or computes each node’s height and maintains:

balance(node) = height(left) - height(right)
balance(node) in {-1, 0, +1}

This local constraint guarantees global height O(log n).

The implementation below stores height in nodes with:

height(NULL) = 0
height(leaf) = 1

This differs by one from the earlier edge-count convention, but balance-factor differences are unchanged. Metadata conventions may differ as long as they are internally consistent.

LL case

Insertion into the left subtree of the left child makes a node left-heavy:

        30             20
       /              /  \
      20      ->     10  30
     /
    10

One right rotation repairs it.

RR case

The symmetric right-right case needs one left rotation:

10                  20
  \                 / \
   20      ->      10  30
     \
      30

LR case

Left-right imbalance bends inward:

      30            30            20
     /              /             / \
    10      ->     20      ->    10  30
      \
       20
 rotate left at 10, then right at 30

RL case

Right-left is symmetric: rotate right at the right child, then left at the unbalanced node.

AVL insertion

Insertion has three stages on the recursive return path:

1. perform ordinary BST insertion;
2. refresh height metadata;
3. rotate if the balance factor lies outside [-1, 1].

At most the nodes on one root-to-leaf path need inspection.

AVL deletion

Deletion performs ordinary BST removal, then may unbalance every ancestor on the return path. Unlike insertion, where the first rebalanced ancestor restores the path height, deletion can require repairs at several levels.

The rotation choice should inspect child balance factors, not the deleted key, because the key may no longer identify the path whose heights changed.

AVL Program

This complete C17 integer AVL set implements search, insertion, deletion, ordered output, and validation of both BST order and stored heights.

#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int key;
    int height;
    struct Node *left;
    struct Node *right;
} Node;

typedef struct {
    Node *root;
    size_t size;
} AVLTree;

static int height(const Node *node) {
    return node == NULL ? 0 : node->height;
}

static int maximum(int a, int b) {
    return a > b ? a : b;
}

static void refresh(Node *node) {
    node->height = 1 + maximum(height(node->left), height(node->right));
}

static int balance(const Node *node) {
    return node == NULL ? 0 : height(node->left) - height(node->right);
}

static Node *node_create(int key) {
    Node *node = malloc(sizeof *node);
    if (node == NULL) {
        return NULL;
    }
    node->key = key;
    node->height = 1;
    node->left = NULL;
    node->right = NULL;
    return node;
}

static Node *rotate_right(Node *y) {
    Node *x = y->left;
    Node *between = x->right;
    x->right = y;
    y->left = between;
    refresh(y);
    refresh(x);
    return x;
}

static Node *rotate_left(Node *x) {
    Node *y = x->right;
    Node *between = y->left;
    y->left = x;
    x->right = between;
    refresh(x);
    refresh(y);
    return y;
}

static Node *rebalance(Node *node) {
    if (node == NULL) {
        return NULL;
    }
    refresh(node);
    int factor = balance(node);

    if (factor > 1) {
        if (balance(node->left) < 0) {
            node->left = rotate_left(node->left);  /* LR */
        }
        return rotate_right(node);                 /* LL or completed LR */
    }
    if (factor < -1) {
        if (balance(node->right) > 0) {
            node->right = rotate_right(node->right); /* RL */
        }
        return rotate_left(node);                    /* RR or completed RL */
    }
    return node;
}

static Node *insert_node(Node *root, int key,
                         bool *inserted, bool *out_of_memory) {
    if (root == NULL) {
        Node *node = node_create(key);
        if (node == NULL) {
            *out_of_memory = true;
        } else {
            *inserted = true;
        }
        return node;
    }

    if (key < root->key) {
        Node *new_left = insert_node(root->left, key,
                                     inserted, out_of_memory);
        if (!*out_of_memory) {
            root->left = new_left;
        }
    } else if (key > root->key) {
        Node *new_right = insert_node(root->right, key,
                                      inserted, out_of_memory);
        if (!*out_of_memory) {
            root->right = new_right;
        }
    } else {
        return root; /* duplicate: no change */
    }

    return *out_of_memory ? root : rebalance(root);
}

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

static Node *erase_node(Node *root, int key, bool *removed) {
    if (root == NULL) {
        return NULL;
    }

    if (key < root->key) {
        root->left = erase_node(root->left, key, removed);
    } else if (key > root->key) {
        root->right = erase_node(root->right, key, removed);
    } else {
        *removed = true;
        if (root->left == NULL || root->right == NULL) {
            Node *child = root->left != NULL ? root->left : root->right;
            free(root);
            return child;
        }

        Node *successor = minimum_node(root->right);
        root->key = successor->key;
        bool internal_removed = false;
        root->right = erase_node(root->right, successor->key,
                                 &internal_removed);
        assert(internal_removed);
    }

    return rebalance(root);
}

static bool validate_node(const Node *root,
                          long long lower, long long upper,
                          size_t *count, int *computed_height) {
    if (root == NULL) {
        *computed_height = 0;
        return true;
    }
    if ((long long)root->key <= lower ||
        (long long)root->key >= upper) {
        return false;
    }

    int left_height, right_height;
    if (!validate_node(root->left, lower, root->key,
                       count, &left_height) ||
        !validate_node(root->right, root->key, upper,
                       count, &right_height)) {
        return false;
    }

    int expected = 1 + maximum(left_height, right_height);
    int factor = left_height - right_height;
    if (root->height != expected || factor < -1 || factor > 1) {
        return false;
    }
    ++*count;
    *computed_height = expected;
    return true;
}

static bool tree_valid(const AVLTree *tree) {
    size_t count = 0;
    int computed_height;
    return tree != NULL &&
           validate_node(tree->root, LLONG_MIN, LLONG_MAX,
                         &count, &computed_height) &&
           count == tree->size;
}

void avl_init(AVLTree *tree) {
    tree->root = NULL;
    tree->size = 0;
}

bool avl_insert(AVLTree *tree, int key) {
    assert(tree_valid(tree));
    bool inserted = false;
    bool out_of_memory = false;
    Node *root = insert_node(tree->root, key,
                             &inserted, &out_of_memory);
    if (out_of_memory) {
        return false;
    }
    tree->root = root;
    if (inserted) {
        ++tree->size;
    }
    assert(tree_valid(tree));
    return inserted;
}

bool avl_remove(AVLTree *tree, int key) {
    assert(tree_valid(tree));
    bool removed = false;
    tree->root = erase_node(tree->root, key, &removed);
    if (removed) {
        --tree->size;
    }
    assert(tree_valid(tree));
    return removed;
}

bool avl_contains(const AVLTree *tree, int key) {
    const Node *node = tree->root;
    while (node != NULL) {
        if (key < node->key) {
            node = node->left;
        } else if (key > node->key) {
            node = node->right;
        } else {
            return true;
        }
    }
    return false;
}

static void inorder(const Node *root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->key);
    inorder(root->right);
}

static void destroy_nodes(Node *root) {
    if (root == NULL) {
        return;
    }
    destroy_nodes(root->left);
    destroy_nodes(root->right);
    free(root);
}

void avl_destroy(AVLTree *tree) {
    destroy_nodes(tree->root);
    avl_init(tree);
}

int main(void) {
    AVLTree tree;
    avl_init(&tree);
    int keys[] = {30, 10, 20, 50, 40, 60, 55};

    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; ++i) {
        if (!avl_insert(&tree, keys[i])) {
            avl_destroy(&tree);
            return EXIT_FAILURE;
        }
    }

    inorder(tree.root); putchar('\n');
    avl_remove(&tree, 30);
    avl_remove(&tree, 60);
    inorder(tree.root); putchar('\n');
    printf("contains 55: %s\n", avl_contains(&tree, 55) ? "yes" : "no");
    avl_destroy(&tree);
    return EXIT_SUCCESS;
}

avl_insert returns false for either a duplicate or allocation failure. A production API may return an enum so callers can distinguish INSERTED, EXISTS, and OUT_OF_MEMORY.

The validator is intentionally Theta(n) and belongs in tests or debug builds. It catches global ordering violations, incorrect height metadata, failed balancing, and size mismatch.

Red-Black Trees

A red-black tree is a BST whose nodes carry one color bit and satisfy rules commonly stated as:

1. every node is red or black;
2. the root is black;
3. null leaves are treated as black;
4. a red node has no red child;
5. every path from a node to a descendant null leaf contains the same number of black nodes.

The number of black nodes on such a path is its black height.

These constraints permit more local height variation than AVL balance, but guarantee that the longest root-to-leaf path is at most twice the shortest. Height remains O(log n).

Rebalancing overview

Insertion begins as BST insertion with a red node. A red node does not change black height, but it may create a red-red parent violation. Repair uses:

• recoloring when the parent and uncle are red;
• rotations plus recoloring when the uncle is black;
• a final black root.

Deletion is more involved because removing a black node can reduce black height on one side. Repairs propagate an extra-black condition through sibling-color cases until invariants are restored.

Full red-black deletion code is long because null/sentinel handling, parent links, colors, and rotations interact. The central data-structure lesson is not to copy cases blindly: each case must preserve BST order, eliminate red-red edges, and equalize black height.

AVL comparison

AVL trees enforce tighter height balance and may offer fewer comparisons for lookup. Red-black trees often use fewer rotations under update-heavy workloads and underpin many standard ordered-map implementations. Both guarantee logarithmic core operations.

Search-Tree Costs

Let h be height and k the number of reported range keys.

Rotations are Theta(1), but finding the update position and walking ancestors still takes logarithmic time in a balanced tree.

Choosing Indexes

Sorted vectors

Sorted arrays provide binary search, compact storage, and fast iteration. Middle insertion and deletion shift values. Search trees trade locality for dynamic logarithmic updates.

Hash tables

Hash tables provide expected constant-time exact lookup and usually use less comparison structure. They do not naturally maintain sorted traversal, bounds, or ranges. Search trees guarantee logarithmic operations under balancing and support order-aware queries.

Heaps

A heap exposes only the highest-priority root efficiently. Searching an arbitrary key is linear. A search tree maintains total key order and supports arbitrary exact lookup, but does not necessarily keep the minimum in an array-friendly complete shape.

B-trees

For storage systems where one pointer traversal may cause an expensive page read, multiway B-trees pack many ordered keys into each node. Binary balanced trees are excellent in-memory foundations; external memory favors higher branching factors.

Map Contracts

A set answers whether a key exists. A map associates each key with a value. The search structure is still determined only by keys, but a useful map interface must also define what happens to values and memory.

Consider inserting key 42 with a new record when key 42 already exists. Reasonable policies include:

• reject the insertion and leave the old record untouched;
• replace the old value and return it to the caller;
• replace and destroy the old value through a registered callback;
• combine the old and new values using a caller-supplied function.

These are observably different operations. A single Boolean result cannot always tell the caller whether a node was created, a value was replaced, or allocation failed. A status can:

typedef enum {
    MAP_INSERTED,
    MAP_REPLACED,
    MAP_UNCHANGED,
    MAP_NO_MEMORY
} MapPutStatus;

Ownership should be equally explicit. One simple contract says the tree copies fixed-size keys and values into each node. Another says it owns heap pointers after successful insertion and invokes destruction callbacks during replacement, removal, and tree destruction. If insertion fails, ownership normally remains with the caller. Document that boundary before writing rotations; otherwise structurally correct code can still leak or double-free payloads.

Removing a key may return its value, destroy it, or merely report success. Returning an owned pointer transfers responsibility back to the caller. A remove_and_destroy operation can be offered separately when callers do not need the value.

Comparator Rules

A generic search tree does not know how to order keys. It asks a comparator:

compare(a, b) < 0  means a comes before b
compare(a, b) == 0 means a and b are the same key
compare(a, b) > 0  means a comes after b

The signs matter; their exact numeric magnitudes do not. The comparator must describe one consistent order:

• comparing a key with itself returns zero;
• if a < b, then b > a;
• if a < b and b < c, then a < c;
• equality used by the map agrees with comparator equality.

Suppose case-insensitive comparison treats "Cat" and "cat" as equal. Then they are one map key even though their bytes differ. Inserting the second spelling follows the duplicate/replacement policy rather than creating a second node. If the application wants both spellings, the comparator must include a tie-breaker or the value must hold a collection.

A comparator that depends on changing external state is dangerous. If a locale, sort mode, or field of an inserted key changes, a node can become stored on the wrong side of an ancestor without any pointer mutation. Keys must remain order-stable while stored. To change such a key, remove it under the old order and insert it under the new order.

For integers, avoid subtraction:

static int compare_int(int a, int b) {
    if (a < b) {
        return -1;
    }
    if (a > b) {
        return 1;
    }
    return 0;
}

return a - b can overflow for distant values and reverse the apparent order. A malformed comparator invalidates search just as surely as a malformed child link.

Node Identity

The common two-child deletion copies the successor’s entry into the target node, then frees the successor node. This preserves the key set, but it has an identity consequence:

before: pointer P refers to node containing key 40
after:  the same pointer P may contain successor key 50
        pointer to the former 50 node is invalid

If callers observe only keys through map operations, this is fine. If callers retain node pointers or attach non-key metadata to a particular physical node, copying entries may violate their expectations.

A transplant deletion physically moves the successor node into the deleted node’s position instead of copying its key. That preserves the successor node’s identity but invalidates the removed target pointer. It also requires careful rewiring of the target’s parent, both children, the successor’s former parent, and balance metadata. Neither policy makes every external pointer stable.

The safest default is to keep nodes private and expose keys, copied values, or documented handles. If handles are allowed, state precisely which operations invalidate them. Rotations generally preserve node addresses in a separately allocated tree; deletion does not. An arena that compacts storage may invalidate every index during a rebuild.

Rank Metadata

Ordered structure can support rank queries by storing the size of every subtree:

typedef struct RankNode {
    int key;
    size_t subtree_size;
    struct RankNode *left;
    struct RankNode *right;
} RankNode;

The added invariant is:

subtree_size(node) = 1 + subtree_size(left) + subtree_size(right)
subtree_size(NULL) = 0

Now select finds the zero-based kth smallest key. At a node, let left_size be the number of keys before the node:

static const RankNode *rank_select(const RankNode *root, size_t k) {
    while (root != NULL) {
        size_t left_size = root->left == NULL
            ? 0
            : root->left->subtree_size;
        if (k < left_size) {
            root = root->left;
        } else if (k == left_size) {
            return root;
        } else {
            k -= left_size + 1;
            root = root->right;
        }
    }
    return NULL;
}

For this tree:

          40 [7]
        /        \
    20 [3]      60 [3]
    /   \       /   \
 10[1] 30[1] 50[1] 70[1]

selecting k = 5 works as follows:

at 40: left_size=3, so skip 20-subtree and 40; k becomes 1
at 60: left_size=1, so k identifies 60

The inverse query, rank(key), accumulates left_size + 1 whenever it moves right. It can return the number of stored keys strictly smaller than key, even when the key is absent. In a balanced tree, both operations take O(log n).

Every insertion and deletion must refresh subtree_size on the changed path. Every rotation must refresh the demoted node before the promoted node, just as with AVL height. A validator should recompute sizes bottom-up rather than trusting stored metadata. Augmentation makes queries faster by making updates and invariants richer.

If duplicates are stored as a multiplicity count, choose whether rank counts distinct keys or total values. For total-value rank, the formula becomes:

subtree_size = count + size(left) + size(right)

That semantic choice must match size() and selection.

Ordered Iteration

An inorder iterator yields one key at a time without materializing the complete sorted sequence. Its state is a stack of ancestors whose left sides have been explored but whose entries have not all been yielded. Initialization pushes the root and every left child. Each next call:

1. pops the top node and yields it;
2. moves to that node’s right child;
3. pushes the right child’s complete left spine.

Across a full traversal, every node is pushed and popped once, so total time is Theta(n) and each call is amortized O(1). The stack uses O(h) space.

Mutation during iteration needs a policy. The simplest robust policy stores a modification counter in the tree and copies it into the iterator. Insertion or deletion increments the tree counter. next rejects the call when the counters differ, preventing it from following a pointer that deletion freed. Value replacement that does not change structure may or may not count as modification depending on whether the iterator exposes values.

A lower-bound iterator can begin at the first key greater than or equal to low: while descending, push a node only when it is a possible answer, then move left; when it is smaller than low, move right without pushing it. Iteration can stop as soon as a yielded key exceeds high. This provides streaming range output with O(h) startup state rather than collecting all results first.

Differential Checks

A sorted dynamic array is an excellent testing oracle for a search tree even though its updates are slower. After each randomly generated insertion or deletion:

• compare operation status with the reference set;
• compare tree size with reference length;
• compare inorder output element by element;
• validate global lower/upper key ranges;
• validate height, color, balance, parent, and subtree-size metadata when present;
• compare minimum, maximum, bounds, rank, and select answers.

Random keys alone may miss structural repairs. Add targeted sequences: increasing order, decreasing order, repeated duplicates, alternating extremes, repeated root deletion, and deletion of nodes with every child configuration. For an AVL or red-black implementation, keep the first failing operation sequence and shrink it to the shortest reproducer; a ten-step trace is much easier to reason about than a million-step random run.

Allocation-failure tests should fail each node creation point in turn. A rejected insertion must leave keys, size, root, and all metadata unchanged. Removal normally allocates nothing and should remain available even when the allocator is exhausted.

Search-Tree Hazards

Local-only validation

Checking each node only against its immediate children misses keys that violate an ancestor’s range. Pass lower and upper bounds through validation.

Ignoring returned roots

Insertion, deletion, and rotations can replace a subtree root. Every caller must store the returned pointer, including the top-level tree object.

Incomplete two-child deletion

Copying the successor into the target without deleting the original successor creates a duplicate and breaks the strict invariant.

Stale metadata

AVL rotations with correct pointers but wrong height-update order may pass inorder tests while later balance decisions fail.

Overflowing comparisons

Avoid comparator code such as return a - b; subtraction can overflow. Return negative, zero, or positive through explicit comparisons.

Ambiguous duplicates

Allowing equality sometimes on the left and sometimes on the right makes search, rotation, and deletion semantics inconsistent. Choose one explicit policy.

Recursive adversarial depth

An ordinary skewed BST can overflow the runtime stack during recursive operations. Balancing or iterative implementations prevent this structural failure mode.

Search-Tree Validation

Exercise shape-changing cases deliberately:

1. empty and singleton trees;
2. duplicate insertion;
3. deletion of leaf, one-child, two-child, and root nodes;
4. minimum and maximum integer keys;
5. LL, RR, LR, and RL insertion sequences;
6. deletion that triggers single and double rotations;
7. repeated root deletion until empty;
8. ranges with no keys, all keys, and boundary keys;
9. sorted insertion into ordinary BST versus AVL;
10. allocation failure at a leaf insertion.

After every randomized update, compare inorder output with a simple sorted reference set and run the structural validator.

Search-Tree Essentials

• A BST’s global invariant partitions keys at every node.
• Search, insertion, and deletion follow one path and cost Theta(h).
• Inorder traversal, bounds, predecessor, successor, and ranges exploit stored order.
• Duplicate behavior is part of the ADT, not an incidental implementation choice.
• Deletion reduces to leaf or one-child removal, using successor or predecessor for the two-child case.
• Rotations preserve inorder order while changing height.
• AVL trees maintain balance factors in [-1,1] and guarantee logarithmic height.
• Red-black trees use color and black-height rules for a looser logarithmic balance.
• Balanced search trees suit workloads that need dynamic updates together with ordered queries.

Search-Tree Problems

Ordering Rules

1. State the global BST invariant using lower and upper ranges.
2. Distinguish predecessor from floor and successor from ceiling.
3. Why can the successor used in two-child deletion have no left child?
4. State the AVL balance-factor rule and the five red-black rules.

Update Traces

5. Insert 40,20,10,30,60,50,70,25,27 into an ordinary BST and draw every shape.
6. Delete the root from the resulting tree using its successor, showing both deletion stages.
7. Trace AVL insertions for one sequence causing each of LL, RR, LR, and RL repair.
8. Delete keys from an AVL tree until one deletion requires repairs at more than one ancestor.

Invariant Failures

9. Construct a tree that passes immediate-child checks but violates the global BST invariant.
10. Diagnose deletion code whose caller ignores the returned subtree root.
11. Explain why refreshing the new root before the demoted node breaks stored AVL heights.
12. Find a duplicate policy that a rotation can violate and reformulate it safely.

Ordered Operations

13. Add minimum, maximum, floor, ceiling, predecessor, successor, and range functions to the AVL implementation.
14. Return distinct insertion statuses for duplicate and allocation failure.
15. Implement an iterative ordinary BST with parent links and a validator for reciprocal links.
16. Augment each AVL node with subtree size and implement selection of the kth smallest key.
17. Store duplicate multiplicities in nodes and update size semantics explicitly.

Index Choices

18. Choose among a sorted vector, AVL tree, red-black tree, and hash table for a read-heavy dictionary that needs prefix ranges.
19. Define ownership and replacement semantics for a tree mapping strings to heap-allocated records.
20. Design an iterator and state which updates invalidate it.
21. Explain when a B-tree is a better ordered structure than a binary tree.

Rotations and Joins

22. Prove that a rotation preserves inorder sequence.
23. Prove that an AVL subtree rooted after rebalance satisfies its local balance rule, assuming both child subtrees were valid.
24. Implement split and join operations for a balanced search tree and use them to express range deletion.