What is a Binary Search Tree?
A Binary Search Tree (BST) is a binary tree where every node satisfies the BST invariant:
- All keys in the left subtree are less than the node's key.
- All keys in the right subtree are greater than the node's key.
This invariant enables efficient search by eliminating half the remaining tree at each step — like binary search, but on a linked structure.
Core operations
Search(key): start at the root. If key < current, go left. If key > current, go right. If key == current, found.
Insert(key): search for the key. When you reach a null pointer, create a new node there.
Delete(key): three cases:
- Leaf node — simply remove it.
- One child — replace the node with its child.
- Two children — find the in-order successor (smallest node in the right subtree), copy its key into the target node, then delete the successor (which has at most one child).
Traversals
- In-order (left, root, right) — visits keys in sorted ascending order.
- Pre-order (root, left, right) — useful for copying/serializing the tree.
- Post-order (left, right, root) — useful for deletion/cleanup.
Complexity
| Operation | Average (balanced) | Worst case (degenerate) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
The worst case occurs when insertions happen in sorted order, turning the tree into a linked list. Self-balancing trees (AVL, Red-Black) prevent this.
Real-Life: Database Indexes
BSTs are the conceptual foundation for database indexes. While real databases use B-Trees or B+Trees (which are wider and disk-friendly), the core search principle is identical.
Where BST-like structures appear:
- TreeMap in Java / std::map in C++ — self-balancing BSTs (Red-Black trees) providing O(log n) sorted operations.
- Database query planning — range queries exploit the sorted property: finding all keys between 100 and 200 means traversing a subtree, not scanning every record.
- In-memory indexes — embedded databases like SQLite use B-tree variants that are generalized BSTs.
File system analogy: think of a library organized by Dewey Decimal. You don't scan every book — you navigate: "Is 510 (Mathematics) left or right of 800 (Literature)?" At each decision point you halve the search space, just like a BST.