A binary search tree (BST) keeps one rule at every node: everything in the left subtree is smaller, everything in the right subtree is larger. To find a key, start at the root and compare: smaller, go left; larger, go right. Each step discards a whole subtree.
Insert works the same way: walk down as if searching, and hang the new node where the search ends. Because the keys are ordered, a BST also gives you what a hash map can't: the smallest and largest key, the next key after a given one, and every key in a range, all by walking the tree.
In real life
Finding all bookings between 9:00 and 11:00, the next scheduled job after now, the nearest price below a limit: questions about order, which a BST answers and a hash map doesn't.
Check yourself
In a BST you search for 60 and the root is 50. Where do you go next, and why?
Why trees need balancing
A BST is only fast if it's short. Insert keys in sorted order, 10, 20, 30, 40, and each new key goes to the right of the previous one: the tree becomes a chain, and searching it is O(n), no better than a list. Real data is often sorted or nearly sorted (timestamps, ids), so this happens in practice.
Self-balancing trees fix it by restructuring themselves after inserts and deletes so the height stays O(log n). AVL trees keep the two subtrees of every node within one level of each other. Red–black trees use a looser rule that needs fewer rotations. Both guarantee O(log n) search, insert and delete in the worst case. You rarely write one yourself: the sorted maps and sets in standard libraries are balanced trees.
In real life
Java's TreeMap and C++'s std::map are red–black trees. The Linux kernel keeps runnable tasks in a red–black tree.
In code: Python · Rust
# No balanced tree in the standard library.
# Options: keep a sorted list with bisect (O(log n) search, O(n) insert),
# or the third-party sortedcontainers package.
import bisect
keys = [10, 20, 40]
bisect.insort(keys, 30) # [10, 20, 30, 40]
use std::collections::BTreeMap; // balanced: a B-tree, see next card
let mut bookings = BTreeMap::new();
bookings.insert(900, "Ann");
bookings.insert(1030, "Bo");
bookings.insert(1500, "Cy");
for (t, who) in bookings.range(900..1100) { println!("{t} {who}"); }
Rust chose B-trees over red–black trees for BTreeMap because they use the CPU cache better.
bisect keeps a Python list sorted; searches are O(log n) but inserts still shift elements.
Check yourself
A plain (unbalanced) BST receives user ids 1, 2, 3, … in increasing order. What happens to lookups?
B-trees: trees for disks and databases
Reading from disk or SSD is far slower than from memory, and you read in pages of several kilobytes. A binary tree with a million keys is about 20 levels deep: 20 page reads per lookup. A B-tree packs hundreds of keys into each node, one node per page, so each node has hundreds of children. A billion keys fit in a tree only 4 or 5 levels deep.
Keys inside a node are kept sorted, and the tree stays perfectly balanced: all leaves are at the same depth. The common variant in databases, the B+ tree, keeps all values in the leaves and links the leaves together, so a range query finds the first key and then walks along the leaves.
In real life
When you add an index on a column in PostgreSQL or MySQL, the database builds a B+ tree. Finding one row among millions takes a handful of page reads, most of them already in memory.
Check yourself
Why do databases use B-trees rather than binary search trees for indexes?
