Search tools and guides ⌘K
II · Trees, with shape

Binary search tree

Sorted, but with shortcuts.

1960 · Conway Berners-Lee · while at Ferranti
The story

Conway Berners-Lee (yes, Tim's father) described the first BST in 1960 while building software for the Ferranti Pegasus. The shape is so natural that several people invented it independently around the same time. Naive BSTs are also famous for degenerating to a linked list when keys arrive sorted.

How it works

Each node has a key and two children: smaller keys go left, larger right. Lookup descends the tree comparing at each step.

Where it lives

Pedagogy and not much else. Every "real" BST in production is balanced (AVL, red-black, B-tree). Naive BSTs survive in toy interpreters and CS courses.

The key insight

Sorted insertion order produces a height-n tree — exactly the disaster a tree was meant to avoid. Self-balancing variants are the only sane production choice.

More in Trees, with shape
AVL tree Always height-balanced, to within one. Red-black tree Almost balanced, much faster to maintain. B-tree / B+ tree The shape of a database index. Heap (binary heap) A priority queue you can grep. Skip list Probabilistic balance, beautifully. Trie (prefix tree) A tree you walk one character at a time. Segment tree Range queries in logarithmic time. Fenwick tree (BIT) Prefix sums, with constant tweaks. Treap BST and heap, secretly the same tree. Splay tree No metadata — and surprising amortised guarantees.
Across the cabinet
III Hash table O(1), almost always. III Cuckoo hashing Two slots, no chains. III Robin Hood hashing Steal from the rich, give to the poor. III Consistent hashing Hashing that survives node changes. III Perfect hashing Zero collisions, by design. IV Bloom filter A set, in a thousandth of the space. IV HyperLogLog Count distinct, in 12 KB. IV Count-Min sketch Approximate frequencies, in tiny memory.
← All data structures