Binary Search Tree

A binary search tree (BST) is a node-based data structure in which each node has at most two children, arranged so that the left subtree contains only keys less than the parent and the right subtree contains only keys greater. This ordering guarantees that search, insertion, and deletion operate in O(h) time, where h is the height of the tree. In the ideal case of a balanced tree, h is logarithmic in the number of nodes, yielding O(log n) operations. But the BST makes no structural guarantees: a sequence of sorted insertions produces a degenerate chain with O(n) performance, worse than a simple linked list because of the overhead of pointer chasing.

The BST is the pedagogical ancestor of the B-tree, but the relationship is evolutionary rather than competitive. Where the BST optimizes for logical elegance — a clean binary division at every step — the B-tree optimizes for physical reality: disk blocks, cache lines, and the memory hierarchy. The BST is what you teach in algorithms courses; the B-tree is what runs in production databases. The gap between them is the gap between theory and practice, and it is bridged not by a single insight but by the accumulated weight of engineering constraints that the BST ignores and the B-tree embraces.