Binary search trees

One rule: smaller left, larger right. Every operation is a walk down one path.

The invariant does everything

• Search / insert / delete: walk down, comparing — O(height)
• Each comparison discards a whole subtree
• min = walk left · max = walk right · successor, ranges
• In-order traversal → sorted output

Watch a BST take shape

Insert 5,3,8,1,4,7,9 — each value walks down (blue) to its spot (green).

The fatal flaw: balance

Sorted input → degenerate linked-list tree → O(n) per op. 291× slower at n=8000.

vs hash table

• BST: ordered — min, max, successor, ranges, sorted iteration — O(log n)
• set/dict: O(1) membership but NO order
• Pay the log factor to get order a hash table can't give at any speed

Takeaway

An ordered container in O(log n) — if it stays balanced. Unbalanced, sorted input kills it. Next: AVL trees keep it balanced.