Binary Search Tree · Data Structures

A binary search tree (BST) is a binary tree with one rule at every node:

All keys in the left subtree are smaller, and all keys in the right subtree are larger.

A BST. Every key left of 50 is smaller than 50; every key right of 50 is larger. The same holds at 30 and 70.

Because of that rule, an inorder traversal of a BST prints the keys in sorted order, and searching can discard half the remaining tree at each step — like binary search.

Try it

Insert, search and delete keys, and watch the tree and its traversals update:

Search and insert

To search, start at the root: go left if the key is smaller, right if it is larger, stop if equal. Insertion searches for the key and attaches a new leaf where the search fell off the tree.

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

typedef struct Node { int key; struct Node *left, *right; } Node;

Node *insert(Node *root, int key) {
    if (root == NULL) {
        Node *n = malloc(sizeof(Node));
        n->key = key; n->left = n->right = NULL;
        return n;
    }
    if (key < root->key)      root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;                                  // duplicates are ignored
}

Node *search(Node *root, int key) {
    while (root != NULL && root->key != key)
        root = (key < root->key) ? root->left : root->right;
    return root;
}

void inorder(Node *r) { if (r) { inorder(r->left); printf("%d ", r->key); inorder(r->right); } }

int main(void) {
    int keys[] = {50, 30, 70, 20, 40, 60, 80, 35};
    Node *root = NULL;
    for (int i = 0; i < 8; i++) root = insert(root, keys[i]);
    printf("Inorder (sorted): ");
    inorder(root);
    printf("\n");
    printf("search 60: %s\n", search(root, 60) ? "found" : "not found");
    printf("search 65: %s\n", search(root, 65) ? "found" : "not found");
    return 0;
}

Output

Inorder (sorted): 20 30 35 40 50 60 70 80 
search 60: found
search 65: not found

Try it Yourself

Minimum and maximum

The smallest key is the leftmost node; the largest is the rightmost:

Node *minNode(Node *r) { while (r && r->left)  r = r->left;  return r; }
Node *maxNode(Node *r) { while (r && r->right) r = r->right; return r; }

Deletion: three cases

Leaf — just remove it.
One child — replace the node with its child.
Two children — replace the node's key with its inorder successor (the smallest key in its right subtree), then delete that successor from the right subtree. (The inorder predecessor works too.)

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

typedef struct Node { int key; struct Node *left, *right; } Node;

Node *insert(Node *r, int k) {
    if (!r) { r = malloc(sizeof(Node)); r->key = k; r->left = r->right = NULL; return r; }
    if (k < r->key) r->left = insert(r->left, k); else if (k > r->key) r->right = insert(r->right, k);
    return r;
}

Node *deleteKey(Node *root, int key) {
    if (root == NULL) return NULL;
    if (key < root->key)      root->left = deleteKey(root->left, key);
    else if (key > root->key) root->right = deleteKey(root->right, key);
    else {
        if (root->left == NULL)  { Node *r = root->right; free(root); return r; }   // cases 1 and 2
        if (root->right == NULL) { Node *l = root->left;  free(root); return l; }
        Node *succ = root->right;                                                   // case 3
        while (succ->left) succ = succ->left;
        root->key = succ->key;
        root->right = deleteKey(root->right, succ->key);
    }
    return root;
}

void preorder(Node *r) { if (r) { printf("%d ", r->key); preorder(r->left); preorder(r->right); } }

int main(void) {
    int keys[] = {50, 30, 70, 20, 40, 60, 80};
    Node *root = NULL;
    for (int i = 0; i < 7; i++) root = insert(root, keys[i]);
    printf("start:            "); preorder(root); printf("\n");
    root = deleteKey(root, 20);  printf("delete 20 (leaf): "); preorder(root); printf("\n");
    root = deleteKey(root, 30);  printf("delete 30 (one):  "); preorder(root); printf("\n");
    root = deleteKey(root, 50);  printf("delete 50 (two):  "); preorder(root); printf("\n");
    return 0;
}

Output

start:            50 30 20 40 70 60 80 
delete 20 (leaf): 50 30 40 70 60 80 
delete 30 (one):  50 40 70 60 80 
delete 50 (two):  60 40 70 80

Try it Yourself

After deleting 50, its inorder successor 60 takes its place as the new root.

Why balance matters

Every BST operation costs O(h), where h is the height.

A balanced BST with n keys has height about log₂ n → operations are O(log n).
Insert keys in sorted order (10, 20, 30, 40…) and every new key goes right: the tree becomes a skewed chain with height n − 1 → O(n), no better than a linked list.

Inserting 10, 20, 30, 40 in order produces a skewed BST — effectively a linked list.

That is why self-balancing trees such as AVL trees (next lesson) and red-black trees exist.

Operation	Balanced BST	Skewed BST
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Inorder traversal	O(n)	O(n)

Test yourself

4 questions · pick an answer to check it instantly

1
Which traversal of a BST lists the keys in ascending order?
2
Insert 45 into the BST with root 50, left child 30 (children 20, 40) and right child 70. Where does 45 go?
3
When deleting a node with two children, what replaces it?
4
What is the worst-case search time in a BST with n nodes?

#Try it

#Search and insert

#Minimum and maximum

#Deletion: three cases

#Why balance matters