Max Independent Set

The Problem That Defines This Chapter

You're a thief robbing houses arranged in a tree (yes, this is LC 337 — House Robber III). Each node holds a value. If you rob a node, you cannot rob any of its direct children. Maximize your total haul.

        3
       / \
      2    3
       \    \
        3    1

On a linked list (House Robber I), this is a classic DP problem. On a general graph, it's NP-hard — no known polynomial solution. But on a tree? \(O(n)\). The reason is the same reason trees are special for everything: subtrees are independent.

The Key Insight: At every node you have exactly two choices — take it (and skip all children) or skip it (and freely choose for each child). These two choices propagate cleanly down because subtrees don't interact.

---

Why Trees Make This Easy

On a general graph, picking one node might affect distant parts of the graph through cycles. On a tree, if you decide to take node \(u\), the only nodes affected are \(u\)'s immediate neighbors. And because trees have no cycles, the constraint doesn't ripple — each subtree can be solved independently.

This is the include-exclude pattern:

• \(\text{dp}[\text{node}][0]\) = best value when we skip this node
• \(\text{dp}[\text{node}][1]\) = best value when we take this node

---

The Recurrence

Skip this node: Each child is free to be taken or skipped. Pick whichever is better for each child.

\[\text{dp}[\text{node}][0] = \sum_{\text{child}} \max(\text{dp}[\text{child}][0],\ \text{dp}[\text{child}][1])\]

Take this node: Collect this node's value, but every child MUST be skipped.

\[\text{dp}[\text{node}][1] = \text{node.val} + \sum_{\text{child}} \text{dp}[\text{child}][0]\]

The answer is \(\max(\text{dp}[\text{root}][0],\ \text{dp}[\text{root}][1])\).

---

Full Trace

Consider this 7-node weighted tree:

          5
        /   \
       3     4
      / \     \
     2   1     6
    /
   7

We process bottom-up (postorder). At each node, compute (skip, take).

Node	Value	Children	dp[child][0], dp[child][1]	skip (dp[node][0])	take (dp[node][1])
7	7	none	—	0	7
2	2	7	(0, 7)	max(0, 7) = 7	2 + 0 = 2
1	1	none	—	0	1
3	3	2, 1	(7, 2), (0, 1)	7 + 1 = 8	3 + 0 + 0 = 3
6	6	none	—	0	6
4	4	6	(0, 6)	max(0, 6) = 6	4 + 0 = 4
5	5	3, 4	(8, 3), (6, 4)	8 + 6 = 14	5 + 8 + 6 = 19

Wait — look at node 5's take value. Taking node 5 (value 5) means skipping children 3 and 4. So we add dp[3][0] = 8 and dp[4][0] = 6, giving \(5 + 8 + 6 = 19\).

Skipping node 5 gives \(\max(8, 3) + \max(6, 4) = 8 + 6 = 14\).

Answer: \(\max(14, 19) = 19\).

Manual verification: Take nodes 5, 7, 1, 6. No two are adjacent. Sum = \(5 + 7 + 1 + 6 = 19\). Correct.

---

The Code (Binary Tree — LC 337)

The function returns a pair: (best if skipped, best if taken).

pair<int, int> solve(TreeNode* root) {
    if (!root) return {0, 0};

    auto [leftSkip, leftTake] = solve(root->left);
    auto [rightSkip, rightTake] = solve(root->right);

    int skipThis = max(leftSkip, leftTake) + max(rightSkip, rightTake);
    int takeThis = root->val + leftSkip + rightSkip;

    return {skipThis, takeThis};
}

int rob(TreeNode* root) {
    auto [skipRoot, takeRoot] = solve(root);
    return max(skipRoot, takeRoot);
}

Complexity: \(O(n)\) time, \(O(h)\) space where \(h\) is the tree height.

---

The Pattern: Include-Exclude

This lesson introduces the framework that powers the entire chapter. Every problem from here — vertex cover, matching, coloring — uses the same skeleton:

1. Define two states per node (included vs excluded, or more).
2. Write a recurrence relating each state to children's states.
3. Solve bottom-up in one postorder pass.

The only things that change are the states and the recurrence. The traversal is always the same.

On general graphs, these problems are NP-hard. On trees, they're \(O(n)\). The tree structure turns exponential search into linear DP.

---

Try It

The starter code has a rob function with a TODO. Implement it using the pair-return pattern.

Input: [3, 2, 3, null, 3, null, 1]
Output: 7

Predict before running: In the tree [3, 2, 3, null, 3, null, 1], which nodes get robbed? Trace through: skip 3 → take 2? No. Take 3 → skip 2 and 3 → take 3 and 1 → total = 3 + 3 + 1 = 7.

Challenge: What if node values can be negative? Does the algorithm still work? Think about whether you'd ever want to "take" a negative node.

Challenge 2: Modify the code to return not just the maximum value, but also which nodes are selected. You'll need to track decisions during the DP and reconstruct the solution top-down.

Edge Cases to Watch For

• Negative node values: You'd never want to "take" a negative node since it reduces your total. The max(skip, take) handles this, but if your DP initializes take without considering the sign, you'll include nodes that hurt the answer.

Problems

Problem	Link	Difficulty
LC 337 — House Robber III	leetcode.com/problems/house-robber-iii	Medium
LC 968 — Binary Tree Cameras	leetcode.com/problems/binary-tree-cameras	Hard
CF 1greedy — Independent Set on Tree	codeforces.com/problemset/problem/1324/F	Medium