Data Structures in Practice

Each node in a binary search tree holds a key larger than everything in its left subtree and smaller than everything in its right.

Search, insertion and deletion follow a single path from the root, giving O(log n) time when the tree is balanced — and O(n) when it degenerates into a list.

Recursive implementations mirror the definition of the tree itself, which makes them short and easy to reason about.