• i. Tree Basics, Diameter and Center: A tree is a connected acyclic graph.
• ii. Tree Isomorphism and Prüfer Codes: Rooted trees are compared by canonical forms built bottom-up (AHU); unrooted trees are rooted at their centre(s) first.
• iii. Lowest Common Ancestor: The deepest common ancestor of $u$ and $v$.
• iv. Euler Tour, Subtree and Path Queries: Flatten the tree in DFS preorder:
• v. Heavy-Light and Long-Path Decomposition: struct HLD {
• vi. Centroid Decomposition: Remove a centroid, recurse on the remaining components.
• vii. Small to Large (DSU on Tree): Answer a query about every subtree by keeping one global structure:
• viii. Virtual Tree: For a set $S$ of $k$ marked vertices, the virtual (auxiliary) tree keeps $S$ plus the LCAs needed to preserve their ancestor structure:
• ix. Kruskal Reconstruction Tree: Run Kruskal, but whenever an edge of weight $w$ joins two components, create a new node with weight $w$ whose children are the two components’ current tree nodes.
• x. Link-Cut Tree: A forest under link and cut with path aggregates, path updates, rerooting, LCA and subtree sizes, each in $O(\log n)$ amortized (Sleator–Tarjan).
• xi. Euler Tour Tree: Keep the Euler tour of every tree of a forest in a balanced sequence (a treap with parent pointers).
• xii. Top Trees: A top tree represents a tree as a hierarchy of clusters (connected edge sets with at most two boundary vertices), built from single edges by two merges: