Binary Search Tree in C – Insert, Search, Delete, and Traversals

A binary search tree (BST) in C is a binary tree where every node satisfies one invariant: all values in the left subtree are less than the node, and all values in the right subtree are greater. This ordering means search, insert, and delete all run in O(h) time — where h is the tree height — which is O(log n) for a balanced tree and O(n) worst-case for a skewed one.

BST Properties

• Left subtree contains only nodes with values less than the root
• Right subtree contains only nodes with values greater than the root
• Each subtree is itself a valid BST (recursive definition)
• No duplicate keys (standard BST; duplicates require extra handling)

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

Inorder traversal → 20 30 40 50 60 70 80  (always sorted!)

BST vs Linear Search Structures

Binary Search Tree Program in C

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

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

/* ── Node creation ────────────────────────────────────────── */
static Node *createNode(int val)
{
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) { fprintf(stderr, "malloc failed\n"); exit(1); }
    n->data  = val;
    n->left  = NULL;
    n->right = NULL;
    return n;
}

/* ── Insert — O(h) ────────────────────────────────────────── */
Node *insert(Node *root, int val)
{
    if (root == NULL)
        return createNode(val);
    if (val < root->data)
        root->left  = insert(root->left,  val);
    else if (val > root->data)
        root->right = insert(root->right, val);
    /* val == root->data: duplicate, ignore */
    return root;
}

/* ── Search — O(h) ────────────────────────────────────────── */
Node *search(Node *root, int val)
{
    if (root == NULL || root->data == val)
        return root;
    if (val < root->data)
        return search(root->left,  val);
    return search(root->right, val);
}

/* ── Find minimum (leftmost node) — O(h) ─────────────────── */
static Node *findMin(Node *root)
{
    while (root->left != NULL)
        root = root->left;
    return root;
}

/* ── Delete — O(h) ────────────────────────────────────────── */
Node *deleteNode(Node *root, int val)
{
    Node *temp;
    if (root == NULL) return NULL;

    if (val < root->data) {
        root->left  = deleteNode(root->left,  val);
    } else if (val > root->data) {
        root->right = deleteNode(root->right, val);
    } else {
        /* Node to delete found */
        if (root->left == NULL) {     /* Case 1 & 2: 0 or 1 child */
            temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            temp = root->left;
            free(root);
            return temp;
        }
        /* Case 3: two children — replace with inorder successor */
        temp = findMin(root->right);
        root->data  = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

/* ── Traversals — O(n) each ───────────────────────────────── */
void inorder(Node *root)
{
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

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

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

/* ── Height — O(n) ────────────────────────────────────────── */
int height(Node *root)
{
    int lh, rh;
    if (root == NULL) return 0;
    lh = height(root->left);
    rh = height(root->right);
    return 1 + (lh > rh ? lh : rh);
}

/* ── Free all nodes — O(n) ────────────────────────────────── */
void freeTree(Node *root)
{
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

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

    /* Build BST */
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Inorder   (sorted): "); inorder(root);   printf("\n");
    printf("Preorder  (root-L-R): "); preorder(root);  printf("\n");
    printf("Postorder (L-R-root): "); postorder(root); printf("\n");
    printf("Height: %d\n\n", height(root));

    /* Search */
    found = search(root, 40);
    printf("Search 40: %s\n", found ? "found" : "not found");
    found = search(root, 45);
    printf("Search 45: %s\n\n", found ? "found" : "not found");

    /* Delete leaf */
    root = deleteNode(root, 20);
    printf("After deleting 20 (leaf):\n");
    printf("Inorder: "); inorder(root); printf("\n\n");

    /* Delete node with one child */
    root = deleteNode(root, 30);
    printf("After deleting 30 (one child):\n");
    printf("Inorder: "); inorder(root); printf("\n\n");

    /* Delete node with two children */
    root = deleteNode(root, 50);
    printf("After deleting 50 (root, two children):\n");
    printf("Inorder: "); inorder(root); printf("\n");

    freeTree(root);
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra -o bst bst.c
./bst

Sample Output

Inorder   (sorted): 20 30 40 50 60 70 80
Preorder  (root-L-R): 50 30 20 40 70 60 80
Postorder (L-R-root): 20 40 30 60 80 70 50
Height: 3

Search 40: found
Search 45: not found

After deleting 20 (leaf):
Inorder: 30 40 50 60 70 80

After deleting 30 (one child):
Inorder: 40 50 60 70 80

After deleting 50 (root, two children):
Inorder: 40 60 70 80

Step-by-Step: Inserting Values 50, 30, 70, 20, 40

insert(NULL, 50): root = [50]

insert([50], 30): 30 < 50 → go left
                  root = [50]
                         /
                       [30]

insert([50], 70): 70 > 50 → go right
                  root = [50]
                         /  \
                       [30] [70]

insert([50], 20): 20 < 50 → left, 20 < 30 → left
                  root = [50]
                         /  \
                       [30] [70]
                       /
                     [20]

insert([50], 40): 40 < 50 → left, 40 > 30 → right
                  root = [50]
                         /  \
                       [30] [70]
                       /  \
                     [20] [40]

The Three Delete Cases Explained

Case 1 — Delete a leaf (no children):

Delete 20 from:       →    Result:
  [30]                         [30]
  /                              \
[20] [40]                       [40]

Just free the node; parent's pointer becomes NULL.

Case 2 — Delete a node with one child:

Delete 30 (only right child 40):

  [50]              [50]
  /        →        /
[30]              [40]
   \
  [40]

Replace the node with its only child.

Case 3 — Delete a node with two children:

Delete 50 (two children):

         [50]                    [60]
        /    \      →           /    \
      [40]  [70]             [40]   [70]
            /  \                       \
          [60] [80]                   [80]

Find inorder successor (smallest value in right subtree = 60).
Copy 60 into the node being deleted.
Then delete 60 from the right subtree (it has at most one child).

Why Inorder Traversal Gives Sorted Output

The BST invariant guarantees that for any node, all left-subtree values come before it and all right-subtree values come after it. The inorder traversal visits: left subtree → root → right subtree. Applied recursively, this visits every node in ascending order — effectively sorting the tree in O(n) without any additional work.

Time and Space Complexity

The worst case (O(n)) occurs when insertions arrive in sorted order — the tree degenerates into a linked list. Self-balancing trees like AVL and Red-Black trees keep height at O(log n) regardless of insertion order, at the cost of more complex rotations on insert/delete.

What This Program Teaches

• Recursive tree algorithms: insert, search, and all traversals are defined in terms of themselves — base case is always the NULL node
• The delete-with-two-children trick: copying the inorder successor’s value avoids structural changes to the left subtree, then reduces to a simpler single-child or leaf deletion in the right subtree
• Inorder → sorted output: the BST invariant directly implies that inorder traversal yields values in ascending order — this is the classic “BST sort”
• Postorder for freeing: you must free children before the parent (postorder) — freeing root first would lose all children

Related Programs

• BFS in C – Breadth First Search — graph traversal that uses a queue
• Singly Linked List in C — linear structure using pointer chains
• Stack Implementation in C
• Queue Program in C
• C Data Structures Aptitude Questions

As an Amazon Associate we earn from qualifying purchases.

Recommended Book

Recursive data structures, pointer-based trees, and dynamic allocation are all covered in The C Programming Language by Kernighan & Ritchie — the tree example in Section 6.5 is the direct predecessor of this code. Also on Amazon.com.