Binary Search Trees

Topic 2 built two extremes: arrays/hash tables (fast lookup, no order) and linked lists (fast front insertion, slow everything else). The binary search tree (BST) is the first structure in the vault to offer $O(h)$ search, insertion, deletion, and ordered traversal simultaneously, where $h$ is the tree's height. This note builds the BST invariant and its core operations, then exposes the structure's central weakness — height depends entirely on insertion order, and an adversarial order collapses $h$ to $\Theta(n)$ — which is precisely the problem red-black trees solve next.