Classification Flowchart
The Point of This Lesson
You've spent 14 chapters learning techniques. Euler tours, segment trees, LCA, rerooting, HLD, centroid decomposition, DSU on tree, virtual trees. The hard part was never implementing them — it was knowing which one to pick.
This lesson is a decision framework. No new algorithms. Just a systematic way to look at any tree problem and identify the right technique in under 60 seconds.
The Flowchart
Work through these questions in order. Each answer narrows the technique space.
Question 1: Is it a subtree problem or a path problem?
Subtree: "for each node, compute something about all nodes in its subtree." The answer depends on descendants only.
Path: "compute something about the path between two specific nodes \(u\) and \(v\)." The answer depends on the chain of ancestors connecting them.
| If subtree → go to Question 2a |
|---|
| If path → go to Question 2b |
Question 2a (Subtree): Single pass or multi-query?
Single pass: You need to compute a value for every node once. No updates, no repeated queries.
- Postorder DFS (Ch 1-3): compute bottom-up. Covers diameter, height, subtree sums, max path sum.
- Rerooting (Ch 9): if the answer changes when the root changes and you need answers for ALL nodes as root.
- DSU on tree (Ch 14): if you need an aggregate (distinct count, most frequent element) over each subtree.
Multi-query with updates: You need to answer queries like "sum of subtree of node \(v\)" after point updates.
- Euler tour + BIT/segment tree (Ch 11): flatten the tree. Subtree of \(v\) is a contiguous range \([\text{tin}(v), \text{tout}(v)]\).
Question 2b (Path): Single query or multi-query?
Single path query: Walk from \(u\) to LCA to \(v\). \(O(n)\) per query is fine.
- LCA + DFS (Ch 7-8): find LCA, walk the path.
Many path queries:
- HLD + segment tree (Ch 14): \(O(\log^2 n)\) per query. Works for max, min, sum, any segment-tree-compatible operation.
- Binary lifting (Ch 8): \(O(\log n)\) per LCA query. Use if you only need the LCA, not a range aggregate on the path.
Question 3: Static tree or dynamic (updates)?
Static: The tree structure doesn't change. Most techniques work.
Dynamic node values: Values on nodes change between queries.
- Euler tour + segment tree with point updates (subtree queries).
- HLD + segment tree with point updates (path queries).
Dynamic tree structure: Edges are added or removed.
- Link-Cut Trees (advanced, beyond this course). Or offline approaches.
Question 4: Does the problem use the BST invariant?
If the tree is a BST and the problem depends on the ordering property (predecessor, successor, rank):
- BST traversal techniques (Ch 5-6): inorder traversal, BST validation, Kth smallest.
- Augmented BSTs with subtree size for order-statistic queries.
If the problem is on a general tree (not a BST), skip this.
Question 5: Do you need range queries on subtrees or paths?
If you need associative aggregates (sum, max, min, GCD) over a range:
- Subtree range query → Euler tour + segment tree / BIT (Ch 11).
- Path range query → HLD + segment tree (Ch 14).
- All-pairs distance counting → Centroid decomposition (Ch 14).
- Queries on a small subset of nodes → Virtual tree (Ch 14).
Quick Reference Table
| Problem pattern | Technique | Chapter |
|---|---|---|
| Compute value for each node from children | Postorder DFS | 1-3 |
| Diameter, max path sum | Postorder returning two values | 3 |
| LCA of two nodes | Binary lifting / Euler tour + RMQ | 7-8 |
| Answer for every possible root | Rerooting DP | 9 |
| Subtree sum/min/max with updates | Euler tour + segment tree | 11 |
| Path sum/min/max with updates | HLD + segment tree | 14 |
| Count paths of length K | Centroid decomposition | 14 |
| Distinct colors per subtree | DSU on tree | 14 |
| Query on small subset in large tree | Virtual tree | 14 |
| Count structurally distinct trees | Catalan / tree hashing | 13 |
10 Problems — Classify Each
Read each problem description. Identify the technique before checking the answer.
Problem 1: "For each node, find the sum of all node values in its subtree."
Answer: Postorder DFS. Single-pass subtree computation. Ch 1-3.
Problem 2: "Given \(q\) queries, each asking for the maximum edge weight on the path from \(u\) to \(v\)."
Answer: HLD + segment tree. Multi-query path aggregation. Ch 14.
Problem 3: "Find the diameter of the tree."
Answer: Postorder DFS returning depth. Two DFS calls or single postorder tracking max depth sum. Ch 3.
Problem 4: "For each node, how many distinct values appear in its subtree?"
Answer: DSU on tree (small-to-large merging). Ch 14.
Problem 5: "Count pairs of nodes whose distance is exactly \(K\)."
Answer: Centroid decomposition. All-pairs distance counting. Ch 14.
Problem 6: "You're given 50 important nodes in a tree of 200,000 nodes. Find the minimum cost to connect all important nodes."
Answer: Virtual tree. Compress to \(\leq 99\) nodes, then sum edge weights. Ch 14.
Problem 7: "Node values can be updated. After each update, answer: what is the sum of all values in the subtree of node 1?"
Answer: Euler tour + BIT. Subtree query with point updates. Ch 11.
Problem 8: "Find the sum of distances from node \(v\) to all other nodes. Answer for every node \(v\)."
Answer: Rerooting. Compute answer at root, then shift to each neighbor. Ch 9.
Problem 9: "Determine if two given unrooted trees are isomorphic."
Answer: Find centroids, root there, AHU hash, compare. Ch 13.
Problem 10: "For each node, find the nearest ancestor whose value is a prime. The tree is static."
Answer: DFS with a stack tracking ancestors. When entering a node, push onto stack. When leaving, pop. Check the stack for the nearest prime ancestor. Ch 10 (ancestor tracking).
The 60-Second Rule
When you see a tree problem in a contest:
- 5 seconds: Subtree or path?
- 5 seconds: One-shot or repeated queries?
- 10 seconds: What's being queried — aggregate, count, existence?
- 10 seconds: Match to technique from the table above.
- 30 seconds: Sketch the approach on paper. Confirm it handles the constraints.
If it doesn't fit any single technique cleanly, it's a composition problem — see the next lesson.
Try It
Take any 5 tree problems you've solved before and classify them using this flowchart. For each, write down:
- Subtree or path?
- Single or multi-query?
- Which technique?
- Which chapter?
Challenge: Find a problem that requires TWO techniques from different chapters. Can you identify the two components and how they compose?
Edge Cases to Watch For
- Dynamic tree structure (edges added/removed): None of the standard techniques (HLD, centroid decomposition, Euler tour) handle this. They all require a fixed tree. If the problem adds or removes edges, you need Link-Cut Trees or offline approaches — applying a static technique to a dynamic tree silently gives wrong answers.
- Problem seems like a path problem but is actually a subtree problem: "All descendants" = subtree query. "Nodes between \(u\) and \(v\)" = path query. Misclassifying the query type leads to choosing the wrong technique entirely.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| LC 124 — Binary Tree Maximum Path Sum | leetcode.com/problems/binary-tree-maximum-path-sum | Hard |
| LC 834 — Sum of Distances in Tree | leetcode.com/problems/sum-of-distances-in-tree | Hard |
| CF 600E — Lomsat gelral | codeforces.com/contest/600/problem/E | Medium |