Max Matching on Trees
Edges, Not Nodes
The previous two lessons selected nodes. This one selects edges. A matching is a set of edges where no two edges share an endpoint. You want the largest matching.
Edges: (1,2), (1,3), (2,4), (2,5), (3,6), (3,7). You can pick (2,4) and (3,6) — that's a matching of size 2. Can you do better? What about (2,4), (1,3), (3,6)? No — edges (1,3) and (3,6) both touch node 3.
What about (2,4), (1,3)? Size 2. Or (2,5), (3,7), and... can we add (1, something)? Node 1 connects to 2 and 3. Node 3 is already used by (3,7). Node 2 is already used by (2,5). So no — size 2 is the max we can get... actually, let's think more carefully with the DP.
The Greedy Intuition: Leaf Stripping
Before the DP, there's a greedy approach worth seeing. It works on general trees and builds intuition.
Algorithm: Find any leaf. Match it to its parent. Remove both nodes. Repeat until no edges remain.
On our tree: leaf 4, match edge (2,4). Remove 4 and 2. Now 5 is disconnected (remove it). The tree is now 1-3 with children 6, 7. Leaf 6, match edge (3,6). Remove 3 and 6. Now 7 and 1 are disconnected.
Result: 2 matched edges. This greedy always finds a maximum matching on trees. Why? Because a leaf has only one edge — if that edge isn't in the matching, the leaf contributes nothing. So greedily matching leaves is never suboptimal.
But the DP approach generalizes better and integrates with the include-exclude framework.
The DP
This time the two states describe whether the node is matched to one of its children:
- \(\text{dp}[\text{node}][0]\) = max matching in this subtree if this node is unmatched (free)
- \(\text{dp}[\text{node}][1]\) = max matching in this subtree if this node is matched to some child
Unmatched: This node doesn't participate in any matched edge. Each child can be matched or unmatched — take the better option.
Matched to a child: Pick one child to match with. That child must be unmatched (since the edge between them uses both). All other children are free.
This looks complicated, but it simplifies. Start with the "unmatched" sum, then for each child \(c\), compute the gain from matching with \(c\):
The best "matched" value is \(\text{dp}[\text{node}][0] + \max_c(\text{gain}(c))\).
Full Trace
| Node | Children | dp[child][0], dp[child][1] | unmatched (dp[node][0]) | best match (dp[node][1]) |
|---|---|---|---|---|
| 4 | none | — | 0 | \(-\infty\) (no child to match) |
| 5 | none | — | 0 | \(-\infty\) |
| 2 | 4, 5 | (0, \(-\infty\)), (0, \(-\infty\)) | 0 + 0 = 0 | match with 4: 1 + 0 + 0 = 1; match with 5: 1 + 0 + 0 = 1; best = 1 |
| 6 | none | — | 0 | \(-\infty\) |
| 7 | none | — | 0 | \(-\infty\) |
| 3 | 6, 7 | (0, \(-\infty\)), (0, \(-\infty\)) | 0 + 0 = 0 | match with 6: 1 + 0 + 0 = 1; match with 7: 1 + 0 + 0 = 1; best = 1 |
| 1 | 2, 3 | (0, 1), (0, 1) | 1 + 1 = 2 | match with 2: 1 + 0 + 1 = 2; match with 3: 1 + 0 + 1 = 2; best = 2 |
At node 1: unmatched gives 2, matched also gives 2. Both achieve matching size 2.
Unmatched path: Don't match edge (1,2) or (1,3). Let node 2 match with a child (say 4), and node 3 match with a child (say 6). Matched edges: (2,4), (3,6).
Matched path: Match edge (1,2), so node 2 is consumed — node 2 is unmatched from its children's perspective. Then node 3 matches with a child. Matched edges: (1,2), (3,6).
Both give size 2. Answer: 2.
The key difference from independent set: here we're selecting edges, and the "matched" state means matched to exactly one specific child. The DP tries all children and picks the best one to match with.
The Code
pair<int, int> solve(TreeNode* root) {
if (!root) return {0, 0};
auto [leftFree, leftMatched] = solve(root->left);
auto [rightFree, rightMatched] = solve(root->right);
int bestLeft = max(leftFree, leftMatched);
int bestRight = max(rightFree, rightMatched);
int unmatched = bestLeft + bestRight;
int matched = -1;
if (root->left) {
matched = max(matched, 1 + leftFree + bestRight);
}
if (root->right) {
matched = max(matched, 1 + rightFree + bestLeft);
}
return {unmatched, max(matched, -1)};
}
int maxMatching(TreeNode* root) {
auto [free, matched] = solve(root);
return max(free, matched);
}
Complexity: \(O(n)\) time, \(O(h)\) space.
Matching vs Independent Set vs Vertex Cover
All three problems share the include-exclude skeleton. Here's how they compare:
| Problem | What we select | "Take" constraint | "Skip" constraint |
|---|---|---|---|
| Max Independent Set | nodes | children must be skipped | children are free |
| Min Vertex Cover | nodes | children are free | children must be taken |
| Max Matching | edges | matched child must be free | children are free |
The skeleton is identical. The recurrence is different. That's the power of this framework.
Try It
Predict before running: What's the maximum matching on a path of 4 nodes? Edges: (1,2), (2,3), (3,4). You can pick (1,2) and (3,4) — size 2. Picking (2,3) blocks both neighbors, so you get only 1. Answer: 2.
Challenge: What's the maximum matching on a star with center \(c\) and \(k\) leaves? Only one edge can be matched (since all edges share the center). So the answer is \(\min(k, 1)\) for \(k \geq 1\).
Challenge 2: A perfect binary tree of height \(h\) has \(2^h - 1\) nodes and \(2^{h} - 2\) edges. What's its maximum matching? Work out the pattern for \(h = 1, 2, 3\).
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CF 1039D — You Are Given a Tree | codeforces.com/problemset/problem/1039/D | Hard |
| SPOJ — Matching on Tree | spoj.com/problems/MATCHING | Medium |
| LC 1353 — Maximum Number of Events | leetcode.com/problems/maximum-number-of-events-that-can-be-attended | Medium |