Lowest Common Ancestor (LCA)

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.