Binary search tree operations

A BST adds ordering to a binary tree so every decision is compare → go left or right. That ordering unlocks predictable search, insert, and delete, plus query helpers such as minimum, maximum, successor (next key in sorted order), and predecessor. This page collects those operations, contrasts them with general binary tree operations, and ships a single C demo you can extend.

Prerequisites: Binary search tree (property), implementations in linked list or sorted array. Structural delete cases mirror binary tree operations, but navigation to the target node follows BST comparisons.

1) How BST operations differ from a plain binary tree

In a general binary tree, finding a value may require visiting many nodes (O(n)). In a BST, if keys are distinct and the tree respects the ordering rule, search, insert, and delete each follow one root-to-node path, length about the tree height h: O(h). A skewed BST can still have h = O(n); balanced BSTs aim for h = O(log n).

2) Search

Recursive form mirrors the definition: compare at the current node, recurse left or right, or stop at a match / NULL. Iterative form replaces the call stack with a loop—same comparisons, constant extra space. Both run in O(h) time.

The demo implements search (recursive) and searchIter (iterative) side by side.

3) Insert

Walk exactly like search until you would step to a missing child; allocate the new node there. If the key already exists, pick a policy (ignore, replace, or allow duplicates with a convention)—the sample code assumes unique keys and skips duplicate inserts implicitly by doing nothing when key == root->data during insert.

4) Delete

Locate the node using BST search, then apply the three structural cases (leaf; one child; two children). For two children, either the inorder successor (min of right subtree) or predecessor (max of left subtree) supplies the replacement key. The downloadable program uses the successor variant, consistent with the other BST lessons.

5) Minimum and maximum

In a BST, the smallest key is the leftmost node reachable by following left pointers from the root. The largest is the rightmost chain. Both are O(h) (or O(log n) when balanced).

6) Successor and predecessor

The successor of a key k is the next larger key in sorted (inorder) order; the predecessor is the next smaller. For a node with a non-NULL right subtree, the successor is the minimum of that right subtree. If there is no right subtree, the successor is the lowest ancestor for which the path went left from ancestor down toward the original node—found by walking from the root and remembering the last node where you branched left because the target was smaller.

Predecessor is symmetric: if the left subtree exists, use maximum of the left subtree; otherwise track the last “right branch” ancestor while searching from the root.

The demo implements successor and predecessor with a single downward walk from the root—no parent pointers needed, but the key is assumed to exist in the tree.

7) Duplicate keys

Duplicates break the clean “left < root < right” picture unless you adopt a tie-break rule (e.g. all equal keys in the right subtree). Interview and teaching code often assumes distinct keys; production designs may store counts at nodes or use secondary ordering.

8) Complete C program

Download binary-search-tree-operations-demo.c and compile with gcc -std=c11 binary-search-tree-operations-demo.c -o bst_ops_demo. It builds the same classic shape used in the other BST demos, prints min/max, compares recursive vs iterative search, prints successor/predecessor for several keys, then deletes a leaf and shows how neighbors change.

// Binary search tree — common operations in C (linked nodes).
// search, insert, delete; min/max; successor and predecessor (inorder neighbors).
// Assume distinct keys. Compile: gcc -std=c11 binary-search-tree-operations-demo.c -o bst_ops_demo

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

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

static Node *createNode(int data) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    n->data = data;
    n->left = n->right = NULL;
    return n;
}

static void freeTree(Node *root) {
    if (!root) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// Smallest key in subtree
static Node *minNode(Node *root) {
    if (!root) {
        return NULL;
    }
    Node *cur = root;
    while (cur->left) {
        cur = cur->left;
    }
    return cur;
}

// Largest key in subtree
static Node *maxNode(Node *root) {
    if (!root) {
        return NULL;
    }
    Node *cur = root;
    while (cur->right) {
        cur = cur->right;
    }
    return cur;
}

Node *search(Node *root, int key) {
    if (!root || root->data == key) {
        return root;
    }
    if (key < root->data) {
        return search(root->left, key);
    }
    return search(root->right, key);
}

// Iterative BST search (same logic, no recursion)
Node *searchIter(Node *root, int key) {
    while (root && root->data != key) {
        if (key < root->data) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return root;
}

Node *insert(Node *root, int key) {
    if (!root) {
        return createNode(key);
    }
    if (key < root->data) {
        root->left = insert(root->left, key);
    } else if (key > root->data) {
        root->right = insert(root->right, key);
    }
    return root;
}

Node *deleteNode(Node *root, int key) {
    if (!root) {
        return NULL;
    }
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        if (!root->left) {
            Node *t = root->right;
            free(root);
            return t;
        }
        if (!root->right) {
            Node *t = root->left;
            free(root);
            return t;
        }
        Node *succ = minNode(root->right);
        root->data = succ->data;
        root->right = deleteNode(root->right, succ->data);
    }
    return root;
}

void inorder(Node *root) {
    if (!root) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

// Next larger key in sorted order (NULL if none). Key must exist in tree.
Node *successor(Node *root, int key) {
    Node *succ = NULL;
    while (root) {
        if (key < root->data) {
            succ = root;
            root = root->left;
        } else if (key > root->data) {
            root = root->right;
        } else {
            if (root->right) {
                return minNode(root->right);
            }
            return succ;
        }
    }
    return NULL;
}

// Next smaller key in sorted order (NULL if none). Key must exist in tree.
Node *predecessor(Node *root, int key) {
    Node *pred = NULL;
    while (root) {
        if (key > root->data) {
            pred = root;
            root = root->right;
        } else if (key < root->data) {
            root = root->left;
        } else {
            if (root->left) {
                return maxNode(root->left);
            }
            return pred;
        }
    }
    return NULL;
}

static void printSuccPred(Node *root, int key) {
    if (!search(root, key)) {
        printf("key %d not in tree — skip succ/pred\n", key);
        return;
    }
    Node *s = successor(root, key);
    Node *p = predecessor(root, key);
    printf("key %d: successor ", key);
    if (s) {
        printf("%d", s->data);
    } else {
        printf("(none)");
    }
    printf(", predecessor ");
    if (p) {
        printf("%d", p->data);
    } else {
        printf("(none)");
    }
    printf("\n");
}

int main(void) {
    printf("=== BST operations demo ===\n\n");

    Node *root = NULL;
    int keys[] = {50, 30, 70, 20, 40, 60, 80};
    for (size_t i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {
        root = insert(root, keys[i]);
    }

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

    Node *mn = minNode(root);
    Node *mx = maxNode(root);
    printf("min = %d, max = %d\n", mn ? mn->data : -1, mx ? mx->data : -1);

    printf("\nsearch(40): %s\n", search(root, 40) ? "found" : "not found");
    printf("searchIter(99): %s\n", searchIter(root, 99) ? "found" : "not found");

    printf("\nSuccessor / predecessor (inorder neighbors):\n");
    printSuccPred(root, 40);
    printSuccPred(root, 50);
    printSuccPred(root, 20);
    printSuccPred(root, 80);

    printf("\nDelete 20 (leaf), then show succ(30):\n");
    root = deleteNode(root, 20);
    printSuccPred(root, 30);

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

9) Typical time costs (BST, height h)

10) Trace: successor of 40

With keys 20 … 80 inserted as in the demo, the tree looks like this:

              50
            /    \
          30      70
         /  \    /  \
       20   40  60   80

Inorder order is 20 30 40 50 60 70 80. The successor of 40 is 50. Algorithmically: node 40 has no right child, so we need the lowest ancestor strictly above 40 on the search path—starting from 50, the search for 40 went left from 50, so 50 is recorded as candidate successor; moving left to 30 and right to 40 finds the node. The answer is 50.