Binary search tree (linked list)

A linked BST stores each key in a struct Node with left and right child pointers. Search, insert, and delete move along a single root-to-node path—O(h) pointer hops—without shifting a whole array like a sorted-key array representation.

Start with Binary search tree for the core property and terminology. This page spells out the pointer-based implementation in one place and matches the same insert/search/delete sequence as the array lesson so you can compare representations side by side.

1) Node = linked record

Each node holds a key and two child pointers. Empty subtree is NULL. The tree is a set of nodes linked by those pointers; “linked list” here means pointer chains in the tree sense, not a linear singly-linked list of all keys.

2) Search

Compare the target with the current node: go left if smaller, right if larger, stop on a match or NULL. Only one branch is taken per level.

3) Insert

Reuse the search comparisons until you fall off at a NULL child; attach a newly allocated node there. No shifting of unrelated keys—only a few pointer writes on the path.

4) Delete (three cases)

Same structure as generic binary-tree delete: leaf (detach), one child (splice), two children (copy inorder successor key from the right subtree’s minimum node, then delete that successor node). The demo uses the successor variant.

5) Inorder and memory

Inorder on a BST lists keys in sorted order. Recursively free with post-order (freeTree): free children before the parent so you never follow a dangling pointer.

6) Complete C program

Download binary-search-tree-linkedlist-demo.c and compile with gcc -std=c11 binary-search-tree-linkedlist-demo.c -o bst_ll_demo. It mirrors the operations demonstrated on the array page: same key sequence, then deletes for leaf, one-child, and two-child nodes.

// Binary search tree (BST) — linked-list / pointer 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-linkedlist-demo.c -o bst_ll_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 (linked list) 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;
}

7) Linked BST vs sorted array (typical)

8) Typical time (BST, height h)

9) Step-by-step walkthrough (matches the demo)

The program inserts 50, 30, 70, 20, 40, 60, 80 in order, then deletes 20 (leaf), 30 (one child after 20 is gone), and 50 (two children, successor step). Tables below trace pointers, not array indices.

➕ Insert sequence (abbreviated path)

Shape after all inserts

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

🔍 Search — key 40

❌ Delete leaf — 20

Locate 20 under 30’s left; replace that child pointer with NULL and free the node. Inorder becomes 30 40 50 60 70 80.

❌ Delete one child — 30

After 20 is removed, 30 has only a right subtree (40). Splice: link 50’s left to 40, free 30. Inorder: 40 50 60 70 80.

❌ Delete two children — 50

Successor in the right subtree is 60 (minimum of 70’s subtree). Copy 60 into the root position, then delete the old 60 node (which becomes a leaf or one-child removal). Final inorder from the demo: 40 60 70 80.

🧾 Final sorted keys (inorder)

40  60  70  80

🧠 Key observations

• Every decision is compare → one pointer follow; no block shift of neighbors.
• Height drives cost—balanced BSTs keep paths short; sorted inserts can degenerate to a chain.
• Pair this page with the array walkthrough to see the same key story with indices and shifts instead of links.