Binary search tree

A binary search tree (BST) is a binary tree with an ordering rule: every key in the left subtree is less than the root key, and every key in the right subtree is greater (assuming distinct keys). That lets search, insert, and structured delete follow a single left/right path instead of scanning all nodes. This page introduces the idea and a full linked C implementation; specialized storage and extra operations follow in the next lessons.

You already know generic binary-tree delete cases and binary trees as pointers. A BST adds comparison-driven navigation: at each node, compare the target key with the stored key and recurse left or right.

1) BST property

For every node t:

• All keys in t->left are < t->data
• All keys in t->right are > t->data

Duplicate keys require a chosen convention (ignore, count, or store in auxiliary structure). The demo assumes keys are unique.

2) Inorder traversal visits keys in sorted order

Inorder (left → root → right) on a BST prints keys in non-decreasing sorted order. That is a classic interview fact and a quick sanity check after insert/delete.

3) Search

Start at the root. If the target equals the current key, stop. If smaller, go left; if larger, go right. If you hit NULL, the key is absent. Time is O(h) where h is height—O(log n) for a balanced tree, O(n) if the tree degenerates to a chain.

4) Insert

Walk the same comparisons as search until you reach a NULL child; allocate a new node there. That preserves the BST property if the key was not already present.

5) Delete

Find the node by BST search, then apply the same three structural cases as on a normal binary tree—except the two-child case usually pulls the inorder successor (smallest key in the right subtree) or the predecessor (largest in the left subtree). The demo uses the successor (minimum of the right subtree), copies its key into the node being removed, then deletes that successor node (which has at most one child).

6) Height and balance (brief)

BST performance depends on height. A sorted insert sequence can produce a tall “list.” Self-balancing BSTs (AVL, red-black, …) keep height logarithmic; this tutorial’s plain BST does not rebalance automatically.

7) Complete C program (linked BST)

Download binary-search-tree-demo.c and compile with gcc -std=c11 binary-search-tree-demo.c -o bst_demo. It implements search, insert, deleteNode, and inorder, with main demonstrating deletes for leaf, one-child, and two-child nodes.

// Binary search tree (BST) — linked representation in C.
// Ordering: left subtree keys < root key < right subtree keys (assume distinct keys).
// Implements search, insert, delete (classic three cases), inorder walk (sorted order).
// Compile: gcc -std=c11 binary-search-tree-demo.c -o bst_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);
}

// Return node with key, or NULL
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);
}

// Smallest node in subtree (used for successor step in delete)
static Node *minNode(Node *root) {
    if (!root) {
        return NULL;
    }
    Node *cur = root;
    while (cur->left) {
        cur = cur->left;
    }
    return cur;
}

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);
}

static int treeHeight(Node *root) {
    if (!root) {
        return 0;
    }
    int lh = treeHeight(root->left);
    int rh = treeHeight(root->right);
    return (lh > rh ? lh : rh) + 1;
}

int main(void) {
    printf("=== Binary search tree demo ===\n\n");

    Node *root = NULL;

    printf("Insert: 50, 30, 70, 20, 40, 60, 80\n");
    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 (sorted): ");
    inorder(root);
    printf("\nHeight: %d\n", treeHeight(root));

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

    printf("\nDelete leaf 20\n");
    root = deleteNode(root, 20);
    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("\nDelete node with one child (30 had only right subtree after 20 removed)\n");
    root = deleteNode(root, 30);
    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("\nDelete node with two children (50)\n");
    root = deleteNode(root, 50);
    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("\nFinal height: %d\n", treeHeight(root));

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

8) Typical time (BST, height h)

9) What’s next

Continue with Binary search tree operations for min/max, successor/predecessor, and operation recap; then map the same logic to an array layout or linked-list / pointer storage. Generic delete shapes are also in Binary tree operations.