CONCEPT · Grandmaster
Trees
also tree · rooted tree
A connected acyclic graph: n nodes, n-1 edges, unique path. Root it to talk about parents, depth, and subtrees. Diameter is a two-sweep, not n BFS.
Intuition
There is exactly one way to walk between two nodes. That uniqueness is every tree algorithm.
When to reach for it
- Hierarchy / org-chart input
- CSES Tree Algorithms
- When a graph is promised to be a tree — skip cycle checks, use parent DFS
Usual pits
- Forgetting the parent edge and infinite-recursing
- Returning height instead of diameter
- Treating the input as already rooted
- Floyd–Warshall on a tree