Chapter 95

Binary Search Trees

A BST is a tree where every node's left subtree contains smaller values and right subtree contains larger values. Search, insert, and delete are O(height) — O(log N) if balanced, O(N) if degenerate.

BST in Contests

In competitive programming, you rarely write a BST from scratch — use std::set, std::map, or std::multiset. But understanding BST structure is essential for segment trees, treaps, and balanced trees.

C++ — ordered set (red-black BST)

set s;
s.insert(10);
s.insert(5);
s.insert(15);

auto it = s.lower_bound(7);   // first ≥ 7 → 10
auto it = s.upper_bound(10);  // first > 10 → 15

// These are O(log N) thanks to the underlying BST

Key Takeaways

→BST: left < root < right. O(height) operations.
→Use std::set/map (C++) or BTreeSet/BTreeMap (Rust) — don't roll your own.