UNIT 12Prerequisite: Unit 11 — Trees75 min read
In Unit 11 we built a binary tree and learned to traverse it. But a plain binary tree has no organisation — elements can be placed anywhere. A Binary Search Tree adds one simple rule on top of everything you already know, and that rule transforms the tree from a random structure into a powerful, searchable, self-organised data structure.
In this unit we learn the BST property, build insert and search from scratch, tackle the tricky delete operation with all three cases, and understand why balance matters — and what happens when a BST goes wrong.
// Section 1
The BST Property — One Rule That Changes Everything
A Binary Search Tree is a binary tree where every node satisfies this rule:
All values in the LEFT subtree are LESS than the node.
All values in the RIGHT subtree are GREATER than the node.
This rule applies at every single node — not just the root. Every node, everywhere in the tree.
✅ Valid BST
Left of 8: 3,1,6 — all < 8 ✓
Right of 8: 10,14 — all > 8 ✓
Left of 3: 1 < 3 ✓ · Right of 3: 6 > 3 ✓
❌ NOT a Valid BST
9 is in left subtree of 8 but 9 > 8 ✗
BST property violated at node 8!
(Even though 9 > 3 locally, globally it breaks the rule)
⚠️ Important
The BST rule is global, not just local. A value in the left subtree must be less than ALL ancestors above it — not just its immediate parent. This is the trap that catches most people when validating a BST.
// Section 2
Insert — Finding the Right Home
Inserting into a BST is elegant. Start at the root and walk down: if the new value is smaller, go left; if larger, go right. Keep going until you reach a NULL — that is where the new node belongs. No shifting, no reorganising. Just walk and attach.
// Inserting 5 into BST with root 8
1
Start at root (8). 5 < 8 → go LEFT
2
At node (3). 5 > 3 → go RIGHT
3
At node (6). 5 < 6 → go LEFT
4
Left of (6) is NULL → insert 5 here ✓
#include <stdio.h>
#include <stdlib.h>
struct BST {
int data;
struct BST *left;
struct BST *right;
};
typedef struct BST BST;
BST* createNode(int value) {
BST *node = (BST*)malloc(sizeof(BST));
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}
/* insert returns the root of the (possibly updated) tree */
BST* insert(BST *root, int value) {
/* base case: found the right spot — create node here */
if (root == NULL) {
return createNode(value);
}
if (value < root->data) {
root->left = insert(root->left, value); /* go left */
} else if (value > root->data) {
root->right = insert(root->right, value); /* go right */
}
/* if value == root->data: duplicate — ignore (or handle as needed) */
return root; /* return unchanged root pointer */
}
/* inorder prints BST values in sorted order */
void inorder(BST *root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
int main() {
BST *root = NULL;
/* build a BST by inserting one at a time */
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 10);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 14);
root = insert(root, 5);
printf("Inorder (sorted): ");
inorder(root);
/* Output: 1 3 5 6 8 10 14 */
return 0;
}
Average Case:O(log n)(balanced tree)
Worst Case:O(n)(degenerate / skewed tree)
🎯 Pro Tip
Inorder traversal of a BST always gives sorted output.This is the most beautiful property of a BST. If you insert 8, 3, 10, 1, 6, 14, 5 in any order, inorder traversal always prints: 1 3 5 6 8 10 14. The tree self-organises by value — you never need to sort explicitly.
// Section 3
Search — O(log n) by Design
Searching in a BST is the same logic as binary search from Unit 10 — but on a tree instead of an array. At each node you either found the target, or the BST property tells you exactly which half to search. You never look at both sides. Half the tree is eliminated at every step.
/* Recursive search */
BST* search(BST *root, int target) {
/* base cases: empty tree or found it */
if (root == NULL) return NULL; /* not found */
if (root->data == target) return root; /* found */
/* BST property tells us which way to go */
if (target < root->data) {
return search(root->left, target); /* must be in left subtree */
} else {
return search(root->right, target); /* must be in right subtree */
}
}
/* Iterative search — same logic, uses a loop */
BST* searchIterative(BST *root, int target) {
while (root != NULL) {
if (root->data == target) return root; /* found */
if (target < root->data) root = root->left; /* go left */
else root = root->right; /* go right */
}
return NULL; /* not found */
}
int main() {
BST *root = NULL;
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 10);
root = insert(root, 1);
root = insert(root, 6);
BST *found = search(root, 6);
if (found) printf("Found: %d\n", found->data); /* Found: 6 */
else printf("Not found\n");
BST *missing = search(root, 99);
if (!missing) printf("99 not in tree\n"); /* 99 not in tree */
return 0;
}
// Searching for 6 in BST [8, 3, 10, 1, 6, 14]
search(8, 6): 6 < 8 → go left
search(3, 6): 6 > 3 → go right
search(6, 6): 6 == 6 → FOUND ✓ (3 steps)
Linear search on same data: up to 6 steps. BST: 3 steps. Gap grows with n.
// Section 4
Delete — Three Cases You Must Know
Deletion is the hardest BST operation because after removing a node, the BST property must still hold for every remaining node. There are exactly three cases depending on how many children the node has. Each case needs a different strategy.
CASE 1Node is a LEAF (no children)Easiest
Just remove it. Set its parent's pointer to NULL. Nothing else needs to change because a leaf has no children that need rehoming.
CASE 2Node has ONE childMedium
Bypass the node — make the parent point directly to the node's only child. The single child takes the deleted node's place. BST property preserved because the child was already correctly positioned relative to the parent.
Before (delete 10, it has one child 14)
→
CASE 3Node has TWO childrenHardest
You cannot just remove it — two subtrees would be left dangling. The trick: find the inorder successor — the smallest value in the right subtree. Copy its value into the current node, then delete the inorder successor (which has at most one child — Case 1 or 2). The BST property is maintained because the inorder successor is larger than everything in the left subtree and smaller than everything else in the right subtree.
What is the inorder successor?
The inorder successor of a node is the smallest node in its right subtree. To find it: go one step right, then go left as far as possible. That leftmost node is the inorder successor.
Before (delete 3 — has children 1 and 6)
Inorder successor of 3
= smallest in right subtree
= go right (6), then left (5)
= 5
Copy 5 → node 3
Delete original 5
→
/* find the minimum value node in a subtree — used for inorder successor */
BST* findMin(BST *root) {
while (root->left != NULL) {
root = root->left; /* go left as far as possible */
}
return root;
}
BST* deleteNode(BST *root, int value) {
if (root == NULL) return NULL; /* value not found */
/* find the node to delete */
if (value < root->data) {
root->left = deleteNode(root->left, value); /* search left */
} else if (value > root->data) {
root->right = deleteNode(root->right, value); /* search right */
} else {
/* found the node to delete — handle the three cases */
/* CASE 1: leaf node — no children */
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
/* CASE 2a: only right child */
if (root->left == NULL) {
BST *temp = root->right;
free(root);
return temp; /* right child takes this node's place */
}
/* CASE 2b: only left child */
if (root->right == NULL) {
BST *temp = root->left;
free(root);
return temp; /* left child takes this node's place */
}
/* CASE 3: two children — find inorder successor */
BST *successor = findMin(root->right); /* smallest in right subtree */
root->data = successor->data; /* copy successor's value here */
root->right = deleteNode(root->right, successor->data); /* delete successor */
}
return root;
}
int main() {
BST *root = NULL;
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 10);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 5);
root = insert(root, 14);
printf("Before delete: "); inorder(root); printf("\n");
/* 1 3 5 6 8 10 14 */
root = deleteNode(root, 3); /* Case 3 — two children */
printf("After delete 3: "); inorder(root); printf("\n");
/* 1 5 6 8 10 14 — 5 replaced 3 */
root = deleteNode(root, 14); /* Case 1 — leaf */
printf("After delete 14: "); inorder(root); printf("\n");
/* 1 5 6 8 10 */
return 0;
}
Average:O(log n)
Worst:O(n)(skewed tree)
// Section 5
The Beautiful Property — Inorder = Sorted
Here is the most elegant fact about BSTs: no matter what order you insert elements, an inorder traversal always returns them in sorted ascending order. Insert 50, 30, 70, 20, 40, 60, 80 — inorder gives 20, 30, 40, 50, 60, 70, 80.
int main() {
BST *root = NULL;
/* insert in random order */
int values[] = {50, 30, 70, 20, 40, 60, 80};
int i;
for (i = 0; i < 7; i++) {
root = insert(root, values[i]);
}
/* inorder always gives sorted output — this is the BST guarantee */
printf("Inorder (sorted): ");
inorder(root);
/* Output: 20 30 40 50 60 70 80 */
/* the tree looks like this:
50
/ \
30 70
/ \ / \
20 40 60 80
*/
return 0;
}
💡 Note
This is why BSTs are used in databases. An ordered set of records (like rows in a table) is stored as a BST or B-Tree. Range queries like WHERE age BETWEEN 20 AND 40 use inorder traversal to find all matching records efficiently — without scanning the entire table.
// Section 6
Balanced vs Unbalanced — When BST Goes Wrong
The O(log n) performance of a BST depends on one assumption: the tree is roughly balanced. If the tree is skewed — all insertions go to one side — the tree becomes a linked list and every operation degrades to O(n). This is the BST's critical weakness.
✅ Balanced BST
Insert: 4, 2, 6, 1, 3, 5, 7
Height = 2
Search = O(log 7) ≈ 3 steps
Wide and short — efficient ✓
❌ Degenerate BST (skewed)
Insert: 1, 2, 3, 4 (sorted order)
Height = 3 (= n-1)
Search = O(n) steps
Tall and thin — basically a list ✗
The fix — Self-Balancing BSTs
Self-balancing trees automatically restructure themselves after each insert/delete to maintain O(log n) height. The two most important ones:
AVL Tree
Strictly balanced — height difference between left and right subtree never exceeds 1. Faster searches. Rebalances more often on insert/delete.
Red-Black Tree
Loosely balanced — uses coloring rules to keep height O(log n). Faster insertions. Used in Java TreeMap, C++ std::map, and Linux kernel process scheduling.
🎯 Pro Tip
For interviews: You will not be asked to implement AVL or Red-Black trees from scratch. But you must know they exist, why they are needed, and what problem they solve. The answer is always: a plain BST degrades to O(n) on sorted input — self-balancing trees guarantee O(log n) always.
// Section 7
Complete BST Program — All Operations Together
#include <stdio.h>
#include <stdlib.h>
struct BST {
int data;
struct BST *left;
struct BST *right;
};
typedef struct BST BST;
BST* createNode(int v) {
BST *n = (BST*)malloc(sizeof(BST));
n->data = v; n->left = n->right = NULL;
return n;
}
BST* insert(BST *root, int v) {
if (!root) return createNode(v);
if (v < root->data) root->left = insert(root->left, v);
else if (v > root->data) root->right = insert(root->right, v);
return root;
}
BST* search(BST *root, int v) {
if (!root || root->data == v) return root;
if (v < root->data) return search(root->left, v);
return search(root->right, v);
}
BST* findMin(BST *root) {
while (root->left) root = root->left;
return root;
}
BST* deleteNode(BST *root, int v) {
if (!root) return NULL;
if (v < root->data) { root->left = deleteNode(root->left, v); }
else if (v > root->data) { root->right = deleteNode(root->right, v); }
else {
if (!root->left && !root->right) { free(root); return NULL; }
if (!root->left) { BST *t = root->right; free(root); return t; }
if (!root->right) { BST *t = root->left; free(root); return t; }
BST *s = findMin(root->right);
root->data = s->data;
root->right = deleteNode(root->right, s->data);
}
return root;
}
int height(BST *root) {
if (!root) return -1;
int l = height(root->left), r = height(root->right);
return 1 + (l > r ? l : r);
}
void inorder(BST *root) {
if (!root) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
int main() {
BST *root = NULL;
int vals[] = {8, 3, 10, 1, 6, 14, 4, 7, 13};
int i, n = 9;
for (i = 0; i < n; i++) root = insert(root, vals[i]);
printf("Inorder: "); inorder(root); printf("\n");
/* 1 3 4 6 7 8 10 13 14 */
printf("Height: %d\n", height(root)); /* 3 */
BST *found = search(root, 6);
printf("Search 6: %s\n", found ? "Found" : "Not found"); /* Found */
root = deleteNode(root, 3); /* delete node with two children */
printf("After delete 3: "); inorder(root); printf("\n");
/* 1 4 6 7 8 10 13 14 */
return 0;
}
// Section 8
BST Operations — Complexity Summary
| Operation | Average (balanced) | Worst (skewed) | Notes |
|---|
| Search | O(log n) | O(n) | Halves the search space each step |
| Insert | O(log n) | O(n) | Walk down to find insertion point |
| Delete | O(log n) | O(n) | Find node + handle 3 cases |
| Inorder traversal | O(n) | O(n) | Must visit every node |
| Find min / max | O(log n) | O(n) | Walk all the way left / right |
| Height | O(n) | O(n) | Must check all paths |
// What's Next
You Are Ready for Unit 13
You now know the BST completely — the property, insert, search, all three delete cases, inorder sorted output, and the balance problem. These are the exact topics that appear in every serious technical interview.
In Unit 13 we cover Heaps — a special tree where the parent is always larger (or smaller) than its children. Heaps power priority queues, heap sort, and Dijkstra's shortest path algorithm. Unlike BSTs, heaps are always balanced — so every operation is guaranteed O(log n).
UP NEXT → UNIT 13
Heaps — Always Balanced, Always Fast
Min heap, max heap, heap as array, insert, delete, heap sort — in C.
🎯 Key Takeaways
- ✓BST rule: every left subtree value is less than the node, every right subtree value is greater — at every node
- ✓The BST rule is global — a value must satisfy the rule relative to ALL its ancestors, not just its parent
- ✓Insert: walk left if smaller, right if larger, until NULL — create node there. O(log n) average
- ✓Search: same as binary search — half the tree eliminated at every step. O(log n) average
- ✓Delete Case 1 (leaf): just remove it — set parent pointer to NULL
- ✓Delete Case 2 (one child): bypass the node — connect parent directly to the single child
- ✓Delete Case 3 (two children): replace with inorder successor (smallest in right subtree), then delete successor
- ✓Inorder traversal of any BST always produces sorted ascending output — the defining property
- ✓Balanced BST: O(log n) for all operations. Skewed BST: O(n) — degrades to a linked list
- ✓Self-balancing trees (AVL, Red-Black) fix the skew problem — used in Java TreeMap, C++ std::map