Trees

A modern hard drive reads about 100 MB per second sequentially, but a single random seek still costs around 10 milliseconds; that gap is roughly seven orders of magnitude. A binary tree of a billion keys has 30 levels, which means 30 random seeks per lookup. **B-Trees and B+ Trees** keep each node fat enough to fill a disk page, branch into hundreds of children, and answer the same lookup in three or four seeks. That is why every relational database you have used relies on this family for its indexes. This lesson covers the B-Tree minimum-degree parameter `t` and the resulting key-and-child counts at every node, the proactive split during insert that keeps the height bounded by `O(log_t n)`, the merge-or-redistribute logic for delete, and the B+ Tree refinement that pushes all data to the leaf level and links those leaves together so range queries become a sequential scan after a single descent. In **Binary Search Tree (BST)**, every node held a single key and at most two children; that geometry is fine for memory but disastrous for disk because each comparison forces a separate I/O. B-Trees flip the design: keep every node wide so a single I/O resolves many comparisons at once. Next, **Splay Tree** explores a third self-balancing strategy in which the tree reshapes itself around access patterns rather than maintaining strict structural invariants.

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.

Every web page you load is a tree (the DOM), every directory you `cd` into is a tree, every JSON document with nested objects is a tree, and every arithmetic expression a compiler parses is a tree. **Binary Tree Fundamentals** turns that ubiquitous shape into a precise data structure where each node has at most two children, named `left` and `right`. This lesson covers the vocabulary you need for the rest of the curriculum (root, leaf, parent, child, sibling, depth, height), the four common shape categories (full, complete, perfect, balanced) and the degenerate case that collapses to a chain, all four canonical traversals (preorder, inorder, postorder, and level-order BFS), and both recursive and iterative implementations of each. You will also analyze why traversals are `O(n)` time but only `O(h)` space when written recursively. In **Queue & Deque**, you saw that a FIFO queue processes items in arrival order; level-order traversal is exactly that pattern applied to tree nodes. In **Hash Map (Dictionary) Basics**, the bucket-by-key idea reappears here when you store parent-pointer mappings or memoize subtree results during a traversal. With binary trees in your toolkit, **Binary Search Tree (BST)** layers an ordering invariant on top to turn the same shape into a logarithmic-time search structure.

Pull the next task in priority order from a stream of millions, and a sorted array gives you `O(1)` extract but `O(n)` insert; a sorted linked list flips the costs but stays linear; a balanced BST hits `O(log n)` for both but with substantial pointer overhead. A **Heap** quietly outperforms all three for this exact workload by storing a complete binary tree in a flat array and keeping just the min (or max) at the root. This lesson covers the heap property, the parent-and-child index formulas (`parent = (i-1)/2`, `left = 2i+1`, `right = 2i+2`) that let array indices encode tree structure with no pointers, sift-up and sift-down for `O(log n)` insert and extract, and the linear-time `heapify` build. You will see how this maps onto the priority queue abstraction and onto interview staples such as top-K elements, K-th largest, merge K sorted lists, and the streaming median with two heaps; on the systems side, the same structure powers Dijkstra and Prim. In **Trees: Binary Tree Fundamentals**, you saw what a complete binary tree is and how to traverse one; the heap reuses that exact shape but stores it implicitly. **Arrays & Strings** is what makes the implicit storage cheap: a flat array gives `O(1)` parent and child access through arithmetic, with no allocations per node. Next, **Binary Search Tree (BST)** trades the heap's partial ordering for a full ordering invariant, unlocking sorted iteration and key-based search at the cost of needing actual pointers.

Cloning a 100k-element segment tree before every update so the previous version stays queryable costs `O(n)` time and space per update, which is unworkable. **Persistent Data Structures** achieve the same 'every past version is still queryable' guarantee in `O(log n)` extra time and space per update by sharing the unchanged subtrees between versions and only allocating new nodes along the path that actually changed. This lesson covers the path-copying technique on a persistent segment tree (each update returns a brand-new root that shares everything except a thin spine of new nodes with the previous version), the `O(log n)` point update and range query on any historical version, persistent arrays built on top of persistent segment trees, and persistent stacks and queues using the cons-list approach from functional programming. You will analyze the total space (`O(n + q log n)` for `q` updates) and apply the structure to k-th smallest in subarrays, time-travel queries, and offline-query reductions. In **Trees: Binary Tree Fundamentals**, a recursive subtree was a self-contained piece of data; structural sharing exploits exactly that property to reuse old subtrees in new versions. **Segment Tree** built the recursive aggregate-over-intervals shape that the persistent variant adapts directly, swapping in-place updates for path copying. Next, **Treap (Randomized BST)** returns to the BST family with a different twist: random priorities for expected balance and `O(log n)` split and merge primitives.

Given an array and a stream of mixed queries (`sum(L, R)`, `min(L, R)`, plus single-index updates), prefix sums answer the queries in `O(1)` but pay `O(n)` for every update, while a raw array does the opposite. Neither extreme is acceptable when both updates and queries are frequent. A **Segment Tree** balances the two: every operation runs in `O(log n)` after an `O(n)` build. This lesson covers the recursive segment-tree shape (a binary tree where each node stores the aggregate over an array interval, and children split the parent's interval in half), the `4n` flat-array layout that maps perfectly onto an iterative or recursive implementation, point update and range query in `O(log n)`, and lazy propagation, where range updates deposit a tag at the highest covering node and push it down only when a later query forces it. You will apply the structure to range sum, range minimum, and range maximum queries, and see why the same template extends to any associative aggregate. In **Arrays & Strings**, a flat array gave you `O(1)` indexed access but no aggregate support; the segment tree layers a hierarchy of precomputed aggregates on top of that array. **Trees: Binary Tree Fundamentals** is where the recursive shape and the `O(h)`-stack traversal pattern came from, and you reuse both directly here. Next, **Fenwick Tree (BIT)** solves a narrower version of the same problem (prefix-only aggregates) with simpler code and half the memory.

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.

Type the letters `a-p-p` into a search box and the autocomplete dropdown produces `apple`, `application`, `apply`, and `appoint` before you finish the next keystroke. The data structure doing that work is a **Trie** (or prefix tree), where every stored word is a path from root to a marked node and every shared prefix is shared in memory exactly once. This lesson covers the trie node layout (a `children` map plus an `isEndOfWord` flag), `insert`, `search`, and `startsWith` operations that all run in `O(m)` for a query of length `m` (independent of how many words the trie holds), and a `delete` that has to be careful not to break paths used by other words. You will also analyze the space behavior, including when a trie wins over a hash set (prefix queries, lexicographic enumeration) and when it loses (memory-tight workloads with no prefix structure to exploit). In **Hash Map (Dictionary) Basics**, you used hashing to answer 'have I seen this exact key' in `O(1)`; a trie answers a strictly richer question (any prefix lookup) by trading `O(1)` exact-match for `O(m)` traversal. **Trees: Binary Tree Fundamentals** introduced the recursive child-pointer pattern, and a trie generalizes it from two children per node to one child per alphabet symbol. With a trie in your toolkit, the curriculum moves on to graph and hash extensions that solve a different family of problems built on the same node-and-edge thinking.

For a set of 32-bit integers, balanced BSTs answer successor and predecessor queries in `log_2(2^32) = 32` comparisons, and hash tables cannot answer those queries at all. A **Van Emde Boas (vEB) tree** answers them in `log_2(log_2(2^32)) = 5`, by recursively halving the bit-length of the universe at each level rather than halving the number of elements. That doubly-logarithmic bound is one of the most striking results in data structure theory. This lesson covers the recursive vEB structure (an integer universe `[0, u-1]` is split into `sqrt(u)` clusters of size `sqrt(u)` plus a summary structure over which clusters are non-empty, applied recursively), the explicit `min` and `max` fields that short-circuit the recursion to a single level when possible, the `O(log log u)` analysis for insert, delete, member, successor, predecessor, min, and max, and the `O(u)` space cost that makes vEB trees practical only for moderate universes. In **Binary Search Tree (BST)**, the height (and thus the operation cost) was governed by the number of stored keys; the vEB tree is governed instead by the size of the integer universe, a fundamentally different parameter. **Heaps & Priority Queue** introduced fast min and max access through a structural invariant; vEB trees push that idea further by also providing fast `successor` and `predecessor` over the same set. With Van Emde Boas, the data structures track is complete; the algorithms track is where these structures come alive in real problem solving.

Finding the lowest common ancestor of two nodes by walking up parent pointers is `O(n)` per query, fine if you ask once but ruinous if you ask a million times on a tree of a million nodes. Binary Lifting precomputes the `2^k`-th ancestor of every node in `O(n log n)` total, then answers LCA in `O(log n)` per query. The same compute-once-then-query-fast pattern unlocks an entire family of advanced tree algorithms. **Advanced Tree Algorithms** covers that family. You will implement LCA via Binary Lifting and via the Euler Tour plus Range Minimum Query approach, where flattening the tree turns subtree queries into array-range queries. Heavy-Light Decomposition splits the tree into chains so path queries become `O(log^2 n)` segment-tree operations. Centroid Decomposition splits a tree of `n` nodes into `O(log n)` layers and powers distance and path-counting queries. The lesson finishes with the rerooting technique for tree DP, which computes DP results for every choice of root in linear total time instead of the naive `O(n^2)`. In **Tree Algorithms**, you mastered recursion-based tree problems and BST operations. This lesson trades simple recursion for preprocessing-and-query structures on top of the tree. Next, **Advanced Search Algorithms** revisits BFS and DFS with heuristic refinements.

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.