Binary Search Tree

Trees O(h) O(n)

Ordered tree where every left subtree is smaller and every right subtree larger — insert, search and delete all follow one root-to-leaf path.

InsertSearchDelete

1/31

Tree empty — 50 becomes the root.

InvariantFor every node, the whole left subtree is smaller and the whole right subtree is larger — so one comparison rules out half the tree.

currentcompareinsertremoverotate

bst.c

typedef struct Node {
    int key;
    struct Node *left, *right;
} Node;
 
Node *insert(Node *root, int key) {
    if (root == NULL)
        return newNode(key);
    if (key < root->key)
        root->left = insert(root->left, key);
    else if (key > root->key)
        root->right = insert(root->right, key);
    return root;
}
 
Node *search(Node *root, int key) {
    while (root && root->key != key)
        root = key < root->key ? root->left
                               : root->right;
    return root;
}
 
Node *deleteNode(Node *root, int key) {
    if (root == NULL) return NULL;
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        if (!root->left)  return root->right;
        if (!root->right) return root->left;
        Node *m = minNode(root->right);
        root->key = m->key;
        root->right = deleteNode(root->right, m->key);
    }
    return root;
}

How Binary Search Tree works

The invariant — left subtree smaller, right subtree larger — turns every operation into a single root-to-leaf walk. Deleting a two-child node swaps in its in-order successor and deletes that instead.

Best case

Balanced tree: O(log n) walks.

Worst case

Sorted insertions degrade it to a linked list: O(n).

When to use it

Ordered maps: range queries, predecessor/successor, sorted iteration — when balancing is added.