The Tree That Became a Line: Binary Search Trees and Balancing

Deep End Era. Engineering with Sankalp · Oct 28, 2026 · 55m

In Accra, Ama Boateng's payment scheduler takes eleven seconds because a payroll customer uploaded salaries sorted by date, and her binary search tree became a forty-thousand-level linked list. In part five of The Deep End's Data Structures series we rotate trees by ear, follow AVL from 1962 Moscow, colour red-black trees in the colours a Xerox PARC printer liked, give random priorities to treaps and let splay trees fold their own paths in half. We meet the Linux scheduler's red-black tree, a textbook deletion that drifted for twenty years, and the NaN that breaks every ordered map. Ama and…