Chapter 2
Trees
Trees are where graph algorithms become honest: no cycles means every traversal is a proof. Learn the six equivalent definitions, then the two traversals, and you already own a surprising share of olympiad problems.
7 pages5,104 words24 problems1 interactive
1Trees: Six Definitions of One ObjectEquivalent characterisations, why each one is the right tool sometimes, and the leaf/degree counting identities.2Distance, Radius, Eccentricitydist on trees and graphs, the centre-of-a-tree theorem, and why two BFS passes are enough.3Counting Trees: Cayley and Prüfern^(n-2) labelled trees, the bijection that proves it, and what the degree sequence looks like from the code.4Depth-First SearchThe recursion that classifies every edge, finds cycles, and produces subtrees, low-links and topological order.5Breadth-First SearchLayers, shortest paths in unweighted graphs, and the multi-source / 0-1 variants that actually win contests.6Tree Diameter in Two PassesThe double-BFS trick, the proof that it is correct, and the DP that beats it when you need more.7Entry/Exit Times and the Euler TourFlatten a tree into an array, and get subtree queries, ancestry tests and LCA-from-RMQ for free.