Binary Search Tree (BST)

Insert the keys 1, 2, 3, 4, 5 into a plain BST in that order and you do not get a tree at all; you get a right-leaning chain with `O(n)` search. The fix is to detect imbalance after every insert or delete and rotate the offending subtree back into shape, which is exactly what a **Balanced BST** does. AVL and Red-Black trees are the two most influential designs in this family. This lesson covers the balance factor (height of left subtree minus height of right subtree), AVL's strict `|bf| <= 1` invariant enforced by the four rotation cases (LL, RR, LR, RL), and Red-Black trees' five color and structural invariants enforced by recoloring plus rotations. You will trace insertions through both schemes, see why Red-Black trees do fewer rotations on average and so are preferred by C++ `std::map` and Java `TreeMap`, and analyze the height bound (`<= 2 log n`) that gives both their worst-case `O(log n)` guarantee. In **Binary Search Tree (BST)**, you implemented search, insert, and delete that respected the ordering invariant but said nothing about shape; the resulting `O(n)` worst case is precisely what self-balancing solves by maintaining a height invariant in addition to the ordering invariant. Next, **B-Trees and B+ Trees** generalize the same balanced-tree idea to nodes that hold many keys at once, an essential design choice for disk-resident data.

Run an inorder traversal on a **Binary Search Tree (BST)** of any size and the keys come out sorted, in `O(n)` time and `O(h)` space, with no separate sort step. That single property (an ordering invariant baked into the structure itself) is what turns a generic binary tree into a logarithmic-time search container that powers Java's `TreeMap`, C++ `std::map`, and the conceptual model behind every database index. This lesson covers the BST property (left subtree keys less than the node, right subtree keys greater), search and insert that follow the invariant, the three deletion cases (leaf, one child, two children resolved by inorder successor or predecessor), and the validation problem that interviewers love because the naive `node.left.val < node.val` check is wrong. You will also analyze the gap between the balanced `O(log n)` and the degenerate `O(n)` chain that motivates the next lesson. In **Trees: Binary Tree Fundamentals**, you implemented preorder, inorder, postorder, and level-order traversals; the BST property is what makes inorder special, because it now produces sorted output for free. Next, **Balanced BST (AVL / Red-Black)** addresses the elephant in the room: an unlucky insertion order can degrade a BST to a linked list, and self-balancing rotations are the fix.

Real workloads are rarely uniform. Web caches, compiler symbol tables, and network routers all access the same handful of items thousands of times in a row before moving on. A **Splay Tree** turns that observation into a balancing strategy: every access (search, insert, or delete) drags the touched node to the root through a sequence of rotations, so frequently used keys stay shallow and effectively pay `O(1)` after the first hit. This lesson covers the three splay rotation cases (zig, zig-zig, and zig-zag) that move a target node toward the root in pairs of levels, the modified search, insert, and delete operations that always end with a splay, and the amortized analysis that yields `O(log n)` per operation across any sequence of `m` operations even though individual operations can be `O(n)` in the worst case. You will also meet the working set theorem, which is the formal version of the temporal-locality intuition. In **Binary Search Tree (BST)**, accesses left the tree shape unchanged; balanced variants enforced strict structural invariants. The splay tree refuses both options and instead lets the access pattern itself reshape the tree, with no balance factor or color bit stored anywhere. Next, **Treap (Randomized BST)** keeps the same single-bit-of-extra-state simplicity but uses random priorities (rather than recent access) to control balance.

Implementing a Red-Black tree from memory under interview pressure is a known-hard task; the rotation cases alone are several hundred lines of careful pointer work. A **Treap** reaches the same expected `O(log n)` height in maybe sixty lines, with no color bits and no balance factor, by giving each node a random priority and asking the tree to satisfy two simple invariants at once. This lesson covers the dual structure (BST order on keys, heap order on randomly assigned priorities), the proof sketch that random priorities yield expected `O(log n)` height because the tree is shaped like a uniform random BST, and the two operations that make treaps unusually flexible: `split(key)` cuts the treap into 'less than' and 'greater or equal' pieces, and `merge` glues two treaps together when one contains only smaller keys. From those two primitives, insert, delete, k-th element, and even range reversal fall out naturally. You will also meet the implicit treap, where positions replace keys and the result behaves like a balanced array supporting `O(log n)` insert-at-index and slicing. In **Binary Search Tree (BST)**, you saw that an unlucky insertion order produced a chain; randomized priorities solve that by making any input look balanced in expectation, the same way randomized quicksort tames adversarial pivots. With treaps in hand, the curriculum next explores structures that exploit very different properties (such as bounded integer universes) to push performance beyond what comparison-based trees can offer.

An invert-binary-tree problem famously got Max Howell rejected from Google in 2015, and the joke landed because the canonical solution is three lines of recursion. Trees show up everywhere in interviews precisely because they reward a particular kind of thinking: the answer for a node is almost always a function of the answers for its left and right subtrees, computed recursively, combined at the parent. **Tree Algorithms** trains that decomposition habit across a wide range of problems. You will implement BST insert, search, delete, validation, and the kth-smallest in-order trick. You will compute lowest common ancestor in both a generic binary tree and a BST. You will measure height, diameter, and width, and walk through path-sum problems, root-to-leaf enumeration, and the deceptively tricky maximum-path-sum-between-any-two-nodes. Structural operations include invert, mirror check, flatten to linked list, and serialize and deserialize. The lesson finishes with reconstructing a tree from inorder plus preorder or inorder plus postorder. In **Trees: Binary Tree Fundamentals**, you learned how nodes, children, and the four traversal orders work. **Recursion Fundamentals** gave you the call-stack mental model that every tree algorithm here relies on; tree recursion is essentially recursion with two recursive calls per frame. Next, **Graph Algorithms (Core)** removes the tree assumption (no cycles, no shared nodes) and tackles the more general traversal problems that result.