Loading…

hardTreesSometimes asked

Maximum Weight Independent Set on a Tree

Q: How do you solve Maximum Weight Independent Set on a Tree using the Brute Force — Enumerate Every Independent Subset approach?

When to use it: Frame the problem with this, then show how local decisions collapse the exponential search into O(n). The definitional approach is to try every subset. **Enumerate.** Each node is independently in or out, so there are `2^n` candidate subsets. For each, confirm no edge connects two chosen nodes and total the weights; keep the best valid total. **Why it is correct but useless at scale.** It literally searches the entire solution space, so it cannot miss the optimum — but `2^n` explodes past a couple dozen nodes. **The observation that rescues it.** Validity is *local*: a chosen node only forbids its direct neighbors. On a tree, a node's only neighbors are its parent and children, and the subtrees hanging off different children share no edges. So the choice inside one child's subtree does not constrain another child's subtree — they interact solely through whether the parent is taken. That independence means we can solve each subtree once and combine, replacing the exponential enumeration with a single pass. Time complexity: O(2^n) worst case. Space complexity: O(n).

Trees & BST · 30 of 41 · 11 min

You are given a tree with n nodes, where node i has weight w[i]. Choose a subset S of nodes maximizing the total weight Σ w[i] over i ∈ S, subject to the constraint that **no two chosen nodes are adjacent** (connected by an edge).

Return the maximum achievable total weight.

In plain English

We want the heaviest set of nodes with no two touching. The crucial structural fact: once we decide whether a node is in the set, its children's options are constrained only by that one decision — taking the node bans its children, skipping it frees them. Subtrees are otherwise independent, so we can solve each subtree and merge the results at the parent. That independence is exactly what makes the tree version polynomial while the general-graph version is NP-hard.

Examples

Example 1

Input: tree rooted at 0: edges 0-1, 0-2, 1-3, 1-4; weights = [3, 4, 2, 1, 6]
Output: 10
Note: Take nodes 0(3), 3(1), and 4(6) = 10. Node 1 (weight 4) is adjacent to 0, 3, and 4, so taking it would block all three; skipping it to take the lighter trio wins. The set {0,3,4} is independent: 0 only touches 1 and 2, both skipped.

Example 2

Input: single node, weight = [5]
Output: 5
Note: One node, no edges — take it.

Example 3

Input: path 0-1-2, weights = [4, 5, 4]
Output: 8
Note: Take the two ends (4 + 4 = 8) rather than the heavier-looking middle (5). The classic House Robber trade-off on a line.

Constraints

1 ≤ n ≤ 10⁵
Weights w[i] can be any integer (including negatives — skipping a negative node is allowed)
The graph is a tree: n − 1 edges, connected, no cycles
Total weight fits in 64-bit (use long in Java)

Clarifying questions4First question: Is it definitely a tree (no cycles)?Explore questions

Q1.Is it definitely a tree (no cycles)?
Yes. On a tree this is O(n) DP; on a general graph maximum independent set is NP-hard, so the tree structure is essential.
Q2.Can weights be negative?
Yes. The 'skip' option contributes 0 for an empty choice, so a node with negative weight is simply never taken — the max handles it automatically.
Q3.Do we need the actual chosen nodes or just the total weight?
Just the weight here. To recover the set, store which branch won at each state and walk back down after the DP.
Q4.Is the tree rooted?
If unrooted, root it at any node and pass the parent into the DFS so we never traverse back up the edge we came from.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Pick a subset of tree nodes with the largest total weight such that no two chosen nodes share an edge. The 'choose or skip' decision at each node depends only on its children, so a post-order DFS with two states per node solves it: dp[node][1] = best when you take node (children must be skipped), dp[node][0] = best when you skip node (each child takes its better option). The answer is max(dp[root][0], dp[root][1]). O(n) time.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can define per-node states that capture the adjacency constraint (taken forces children skipped) and combine subtree results in a single post-order pass — recognizing this is House Robber lifted onto a tree.

Where candidates slip

Using only one state per node (losing the information of whether the node was taken), returning dp[root][1] instead of the max of both states, or recursing without a parent guard and looping over the edge back to the parent.

How to stand out

Name it as House Robber III generalized, state the two recurrences crisply, justify post-order, and note that maximum independent set is NP-hard on general graphs but linear on trees because of the no-cycle structure.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Enumerate Every Independent Subset	`O(2^n) worst case`	`O(n)`	Frame the problem with this, then show how local decisions collapse the exponential search into O(n).	Read
2	Tree DP — Two States per Node (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. 'Post-order DFS; each node returns the best taking it and the best skipping it.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Two states bubbling up the tree

How to read it:Each node returns (skip, take). Taking a node adds each child's skip; skipping adds each child's max.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Enumerate Every Independent Subset

TimeO(2^n) worst caseSpaceO(n)

Frame the problem with this, then show how local decisions collapse the exponential search into O(n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Every node is either in the set or out. Try all 2^n assignments and keep the heaviest that is independent.

2Hint 2Explore hint

Check independence by verifying no edge has both endpoints chosen, then sum the weights.

3Hint 3Explore hint

Exponential — but it reveals the real structure: a node's validity depends only on its neighbors, so the decisions are local.

A · Core idea

The definitional approach is to try every subset.

Enumerate. Each node is independently in or out, so there are 2^n candidate subsets. For each, confirm no edge connects two chosen nodes and total the weights; keep the best valid total.

Why it is correct but useless at scale. It literally searches the entire solution space, so it cannot miss the optimum — but 2^n explodes past a couple dozen nodes.

The observation that rescues it. Validity is local: a chosen node only forbids its direct neighbors. On a tree, a node's only neighbors are its parent and children, and the subtrees hanging off different children share no edges. So the choice inside one child's subtree does not constrain another child's subtree — they interact solely through whether the parent is taken. That independence means we can solve each subtree once and combine, replacing the exponential enumeration with a single pass.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

path 0-1-2, weights = [4, 5, 4]

{}

weight 0

Statevalid

Final result8

C · Code with teaching comments

Reference implementation previewimport java.util.*; class BruteForceMIS { int maxWeight(int n, int[][] edges, int[] w) { int best = 0;Explore the full code

solution.javaJava

Brute Force — Enumerate Every Independent Subset — reference

3 teaching notes

1
import java.util.*;
2
 
3
class BruteForceMIS {
4
    int maxWeight(int n, int[][] edges, int[] w) {
5
        int best = 0;
6
        // Every subset of nodes as a bitmask — 2^n of them.
7
        for (int mask = 0; mask < (1 << n); mask++) {
8
            boolean ok = true;
9
            for (int[] e : edges) {
10
                // Reject any subset that includes both ends of an edge.
11
                if (((mask >> e[0]) & 1) == 1 && ((mask >> e[1]) & 1) == 1) {
12
                    ok = false; break;   // both endpoints chosen
13
                }
14
            }
15
            if (!ok) continue;
16
            int sum = 0;
17
            for (int i = 0; i < n; i++) {
18
                if (((mask >> i) & 1) == 1) sum += w[i];
19
            }
20
            // Keep the heaviest independent subset.
21
            best = Math.max(best, sum);
22
        }
23
        return best;
24
    }
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(2^n) worst case timeO(n) spaceOpen the invariant and proofExplore the proof

The leap from exponential to linear is the realization that the no-adjacency constraint is purely local on a tree: fixing one node's in/out status fully decouples its children's subtrees. Capture that one bit of context as a DP state and the search collapses.

ComplexityO(2^n) worst case time, O(n) space — There are 2^n subsets; validating and summing each is O(n), giving O(n·2^n). Hopeless beyond ~25 nodes, but it defines what 'optimal' means.

E · Edge cases and pitfalls3Treating it as feasible for large n — 2^n is exponential.Explore edge cases

Pitfalls

Treating it as feasible for large n — 2^n is exponential.
Forgetting the empty set (weight 0) as a valid baseline for all-negative weights.
Re-checking the same subtree decisions across masks — the redundancy the DP removes.

03.2

Approach 2 of 2 · Optimal

Tree DP — Two States per Node (Optimal)

TimeO(n)SpaceO(n)

The answer they want. 'Post-order DFS; each node returns the best taking it and the best skipping it.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Define two values per node: dp[node][1] = best total in node's subtree WHEN node is taken; dp[node][0] = best WHEN node is skipped.

2Hint 2Explore hint

If you take the node, no child may be taken, so add each child's dp[child][0]. If you skip the node, each child is free, so add max(dp[child][0], dp[child][1]).

3Hint 3Explore hint

Post-order: compute both children's states first, then the parent's. The answer is max(dp[root][0], dp[root][1]).

A · Core idea

Encode the only thing a child needs to know about its parent's decision as a per-node state, and the subtrees decouple.

The two states. For each node define:

dp[node][1] — the maximum total weight in node's subtree given that `node` is taken.
dp[node][0] — the maximum total weight in node's subtree given that `node` is skipped.

The recurrences. Process children first (post-order), then combine:

If node is taken, none of its children may be taken (they are adjacent to it). So dp[node][1] = w[node] + Σ dp[child][0] over all children.
If node is skipped, each child may independently do whatever is best for it. So dp[node][0] = Σ max(dp[child][0], dp[child][1]).

Why the children are independent. Two children of the same node live in disjoint subtrees joined only through that node. Once the parent's taken/skipped status is fixed, no constraint links one child's subtree to another's, so we can optimize each child separately and add the results. This is precisely why a single bit of state per node is enough.

Why post-order. Each recurrence reads the children's dp values, so every child must be finished before its parent — left/right (or all children) first, then the node.

The answer. At the root there is no parent to constrain it, so either state is allowed: max(dp[root][0], dp[root][1]). Returning only dp[root][1] wrongly forces the root into the set.

Negative weights for free. Because dp[node][0] sums max(skip, take) and a taken negative node would only lower the total, the max naturally declines to take nodes that hurt — no special case needed.

This is House Robber on a tree. House Robber III is exactly this with weights on a binary tree; the line version (plain House Robber) is the same recurrence on a path. Recognizing the family is the fastest way to the right code.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

path 0-1-2 rooted at 0, weights = [4, 5, 4]

Interactive diagram

States on the path 0-1-2

node 2 (leaf)

Active call / nodeSupporting contextReturned stateNot active

Leaf 2 returns (0,4); node 1 returns (4,5); root 0 returns (5,8). Answer 8 = take ends 0 and 2.

Final result8

C · Code with teaching comments

solution.javaJava

Tree DP — Two States per Node (Optimal) — optimal

6 teaching notes

1
import java.util.*;
2
 
3
class TreeMIS {
4
    private List<List<Integer>> adj;
5
    private long[] w;
6
    private long[][] dp;   // dp[node][0]=skip, dp[node][1]=take
7
 
8
    long maxWeight(int n, int root, int[][] edges, long[] weights) {
9
        adj = new ArrayList<>();
10
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
11
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
12
        this.w = weights;
13
        // Two states per node: index 0 = skip this node, index 1 = take it.
14
        dp = new long[n][2];
15
 
16
        // Iterative post-order to avoid stack overflow on a chain of 10^5 nodes.
17
        int[] parent = new int[n];
18
        int[] order = new int[n];
19
        int idx = 0;
20
        Deque<Integer> stack = new ArrayDeque<>();
21
        boolean[] seen = new boolean[n];
22
        stack.push(root); parent[root] = root; seen[root] = true;
23
        while (!stack.isEmpty()) {            // BFS/DFS order for processing
24
            int node = stack.pop();
25
            order[idx++] = node;
26
            for (int next : adj.get(node)) {
27
                if (!seen[next]) { seen[next] = true; parent[next] = node; stack.push(next); }
28
            }
29
        }
30
        // Process children before parents: reverse discovery order works for a tree.
31
        // Reverse discovery order processes children before parents — an iterative
32
        // post-order.
33
        for (int i = n - 1; i >= 0; i--) {
34
            int node = order[i];
35
            long take = w[node];
36
            long skip = 0;
37
            for (int child : adj.get(node)) {
38
                // Skip the edge back to the parent so we only recurse into real
39
                // children.
40
                if (child == parent[node]) continue;
41
                // Taking node forbids each child → add the child's skip value.
42
                take += dp[child][0];
43
                // Skipping node frees each child → add the child's better option.
44
                skip += Math.max(dp[child][0], dp[child][1]);
45
            }
46
            dp[node][1] = take;
47
            dp[node][0] = skip;
48
        }
49
        // Root has no parent, so either state is allowed — take the max.
50
        return Math.max(dp[root][0], dp[root][1]);
51
    }
52
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.52 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The whole trick is choosing a state that makes subtrees independent. 'Taken vs skipped' is the minimal context a parent must hand down, because adjacency only reaches one level. Once decisions decouple, an NP-hard general-graph problem becomes a linear post-order scan — a recurring lesson in tree DP.

ComplexityO(n) time, O(n) space — A single post-order DFS visits each node once and does O(deg) work combining its children; summed over the tree that is O(n) total (each edge handled once). The recursion stack and dp arrays are O(n) space.

E · Edge cases and pitfalls7single node weight 5 — Leaf: take=5, skip=0 → max(0,5)=5.Explore edge cases

Edge cases handled

single node weight 5Leaf: take=5, skip=0 → max(0,5)=5.
all weights negativeEvery take is dominated by skip (0), so the answer is 0 — the empty set, which is valid.
star graph (center + many leaves)Either take the center (skip all leaves) or skip the center (take every positive leaf); the DP compares both.

Pitfalls

Using one state per node — you lose whether the node was taken, breaking the parent's recurrence.
Returning dp[root][1] instead of max(dp[root][0], dp[root][1]).
Recursing without a parent check — infinite loop over the parent edge on an undirected adjacency list.
Deep recursion on a chain of 10⁵ nodes — use an iterative post-order to avoid stack overflow.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class TreeMIS { private List<List<Integer>> adj; private long[] w;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

class TreeMIS {
    private List<List<Integer>> adj;
    private long[] w;
    private long[][] dp;   // dp[node][0]=skip, dp[node][1]=take

long maxWeight(int n, int root, int[][] edges, long[] weights) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        this.w = weights;
        dp = new long[n][2];

// Iterative post-order to avoid stack overflow on a chain of 10^5 nodes.
        int[] parent = new int[n];
        int[] order = new int[n];
        int idx = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        boolean[] seen = new boolean[n];
        stack.push(root); parent[root] = root; seen[root] = true;
        while (!stack.isEmpty()) {            // BFS/DFS order for processing
            int node = stack.pop();
            order[idx++] = node;
            for (int next : adj.get(node)) {
                if (!seen[next]) { seen[next] = true; parent[next] = node; stack.push(next); }
            }
        }
        // Process children before parents: reverse discovery order works for a tree.
        for (int i = n - 1; i >= 0; i--) {
            int node = order[i];
            long take = w[node];
            long skip = 0;
            for (int child : adj.get(node)) {
                if (child == parent[node]) continue;
                take += dp[child][0];
                skip += Math.max(dp[child][0], dp[child][1]);
            }
            dp[node][1] = take;
            dp[node][0] = skip;
        }
        return Math.max(dp[root][0], dp[root][1]);
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

One state per node

A child needs to know its own best total in BOTH cases — when the parent is taken (child forced to skip) and when the parent is skipped (child free). Collapsing to a single value loses the case the parent needs.

Explore the code comparison

Don't write this

def dfs(node, parent):
    best = w[node]
    for c in children: best += dfs(c, node)   # single value, no skip case
    return best

Write this instead

def dfs(node, parent):
    take, skip = w[node], 0
    for c in children:
        ct, cs = dfs(c, node)            # (take, skip) for the child
        take += cs
        skip += max(ct, cs)
    return take, skip

Returning only the taken state

The root has no parent constraining it, so skipping the root can be better (e.g. a heavy node deep in the tree). Return the max of both root states.

Explore the code comparison

Don't write this

return dp[root][1];                 // forces the root into the set

Write this instead

return Math.max(dp[root][0], dp[root][1]);

No parent guard on an undirected tree

Adjacency lists store each edge in both directions. Without skipping the parent, the DFS revisits the parent as a 'child' and recurses forever.

Explore the code comparison

Don't write this

for child in adj[node]:
    dfs(child, node)               # also recurses into the parent

Write this instead

for child in adj[node]:
    if child == parent:
        continue
    dfs(child, node)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Post-order tree DP with two states per node: taken vs not taken

Code pattern to memorize

dfs(node, parent):
    take = weight[node]
    skip = 0
    for child != parent:
        dfs(child, node)
        take += dp[child][0]            # child must be skipped
        skip += max(dp[child][0], dp[child][1])  # child free to choose
    dp[node][1] = take
    dp[node][0] = skip

Rules to remember

1Two states per node: taken forces every child to the skipped state; skipped lets each child take its own max.
2Combine children independently — subtrees do not interact except through the parent's choice.
3Use post-order: a node's dp needs both children's dp values first.
4The answer is max(dp[root][0], dp[root][1]), not just dp[root][1].
5On a general (unrooted) tree, root it anywhere and pass the parent to avoid walking back up an edge.

Use this pattern when

Optimize over subsets of tree nodes with an adjacency (no-two-adjacent) constraint
House-Robber-style problems generalized from a line to a tree
Any 'select/skip with a local conflict' optimization on a tree
Counting or weighting where each node's choice only constrains its neighbors

Choose another pattern when

Graph has cycles (not a tree) → maximum independent set is NP-hard in general; tree DP relies on no cycles
Constraint spans non-adjacent nodes (e.g. distance ≤ 2) → states must encode more than taken/skipped
You need the actual set, not just its weight → store back-pointers / reconstruct after the DP
The line case (array, not tree) → 1-D House Robber DP is simpler

Interview takeaway

Tree DP is 'solve each subtree, combine at the parent'. Encoding the parent's choice as a small state (here, taken or skipped) makes the children independent, so one post-order pass with O(1) work per node gives an O(n) optimum to a problem that is NP-hard on general graphs.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTree DP with per-node states that capture the parent's decision. Here two states (taken forces children skipped, skipped frees them) make subtrees independent, so one post-order pass gives an O(n) optimum to a problem that is NP-hard on general graphs. Same engine as House Robber III and tree vertex cover.

Practice queueDirect variations and pattern siblings

Direct follow-ups

House Robber III
Coming soon
This exact DP on a binary tree — return (robbed, notRobbed) from each node.
House Robber
Coming soon
The line (path) special case: the same take/skip recurrence over an array.
Minimum Vertex Cover on a Tree
Coming soon
Complement view: minimum vertex cover = n − maximum independent set (unweighted) via the same DP.
Binary Tree Cameras
Coming soon
Three-state tree DP (covered/has-camera/uncovered) — same post-order combine, richer states.

Same pattern

←

Segment Tree for Range Sum

Continue · Next problem

Binary Search Tree: Insertion

hardTreesSometimes asked

Maximum Weight Independent Set on a Tree

Trees & BST · 30 of 41 · 11 min

Return the maximum achievable total weight.

In plain English

Examples

Example 1

Input: tree rooted at 0: edges 0-1, 0-2, 1-3, 1-4; weights = [3, 4, 2, 1, 6]
Output: 10
Note: Take nodes 0(3), 3(1), and 4(6) = 10. Node 1 (weight 4) is adjacent to 0, 3, and 4, so taking it would block all three; skipping it to take the lighter trio wins. The set {0,3,4} is independent: 0 only touches 1 and 2, both skipped.

Example 2

Input: single node, weight = [5]
Output: 5
Note: One node, no edges — take it.

Example 3

Input: path 0-1-2, weights = [4, 5, 4]
Output: 8
Note: Take the two ends (4 + 4 = 8) rather than the heavier-looking middle (5). The classic House Robber trade-off on a line.

Constraints

1 ≤ n ≤ 10⁵
Weights w[i] can be any integer (including negatives — skipping a negative node is allowed)
The graph is a tree: n − 1 edges, connected, no cycles
Total weight fits in 64-bit (use long in Java)

Clarifying questions4First question: Is it definitely a tree (no cycles)?Explore questions

Q1.Is it definitely a tree (no cycles)?
Yes. On a tree this is O(n) DP; on a general graph maximum independent set is NP-hard, so the tree structure is essential.
Q2.Can weights be negative?
Yes. The 'skip' option contributes 0 for an empty choice, so a node with negative weight is simply never taken — the max handles it automatically.
Q3.Do we need the actual chosen nodes or just the total weight?
Just the weight here. To recover the set, store which branch won at each state and walk back down after the DP.
Q4.Is the tree rooted?
If unrooted, root it at any node and pass the parent into the DFS so we never traverse back up the edge we came from.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Enumerate Every Independent Subset	`O(2^n) worst case`	`O(n)`	Frame the problem with this, then show how local decisions collapse the exponential search into O(n).	Read
2	Tree DP — Two States per Node (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. 'Post-order DFS; each node returns the best taking it and the best skipping it.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Two states bubbling up the tree

How to read it:Each node returns (skip, take). Taking a node adds each child's skip; skipping adds each child's max.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Enumerate Every Independent Subset

TimeO(2^n) worst caseSpaceO(n)

Frame the problem with this, then show how local decisions collapse the exponential search into O(n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Every node is either in the set or out. Try all 2^n assignments and keep the heaviest that is independent.

2Hint 2Explore hint

Check independence by verifying no edge has both endpoints chosen, then sum the weights.

3Hint 3Explore hint

Exponential — but it reveals the real structure: a node's validity depends only on its neighbors, so the decisions are local.

A · Core idea

The definitional approach is to try every subset.

Enumerate. Each node is independently in or out, so there are 2^n candidate subsets. For each, confirm no edge connects two chosen nodes and total the weights; keep the best valid total.

Why it is correct but useless at scale. It literally searches the entire solution space, so it cannot miss the optimum — but 2^n explodes past a couple dozen nodes.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

path 0-1-2, weights = [4, 5, 4]

{}

weight 0

Statevalid

Final result8

C · Code with teaching comments

Reference implementation previewimport java.util.*; class BruteForceMIS { int maxWeight(int n, int[][] edges, int[] w) { int best = 0;Explore the full code

solution.javaJava

Brute Force — Enumerate Every Independent Subset — reference

3 teaching notes

1
import java.util.*;
2
 
3
class BruteForceMIS {
4
    int maxWeight(int n, int[][] edges, int[] w) {
5
        int best = 0;
6
        // Every subset of nodes as a bitmask — 2^n of them.
7
        for (int mask = 0; mask < (1 << n); mask++) {
8
            boolean ok = true;
9
            for (int[] e : edges) {
10
                // Reject any subset that includes both ends of an edge.
11
                if (((mask >> e[0]) & 1) == 1 && ((mask >> e[1]) & 1) == 1) {
12
                    ok = false; break;   // both endpoints chosen
13
                }
14
            }
15
            if (!ok) continue;
16
            int sum = 0;
17
            for (int i = 0; i < n; i++) {
18
                if (((mask >> i) & 1) == 1) sum += w[i];
19
            }
20
            // Keep the heaviest independent subset.
21
            best = Math.max(best, sum);
22
        }
23
        return best;
24
    }
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(2^n) worst case timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(2^n) worst case time, O(n) space — There are 2^n subsets; validating and summing each is O(n), giving O(n·2^n). Hopeless beyond ~25 nodes, but it defines what 'optimal' means.

E · Edge cases and pitfalls3Treating it as feasible for large n — 2^n is exponential.Explore edge cases

Pitfalls

Treating it as feasible for large n — 2^n is exponential.
Forgetting the empty set (weight 0) as a valid baseline for all-negative weights.
Re-checking the same subtree decisions across masks — the redundancy the DP removes.

03.2

Approach 2 of 2 · Optimal

Tree DP — Two States per Node (Optimal)

TimeO(n)SpaceO(n)

The answer they want. 'Post-order DFS; each node returns the best taking it and the best skipping it.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Define two values per node: dp[node][1] = best total in node's subtree WHEN node is taken; dp[node][0] = best WHEN node is skipped.

2Hint 2Explore hint

If you take the node, no child may be taken, so add each child's dp[child][0]. If you skip the node, each child is free, so add max(dp[child][0], dp[child][1]).

3Hint 3Explore hint

Post-order: compute both children's states first, then the parent's. The answer is max(dp[root][0], dp[root][1]).

A · Core idea

Encode the only thing a child needs to know about its parent's decision as a per-node state, and the subtrees decouple.

The two states. For each node define:

dp[node][1] — the maximum total weight in node's subtree given that `node` is taken.
dp[node][0] — the maximum total weight in node's subtree given that `node` is skipped.

The recurrences. Process children first (post-order), then combine:

If node is taken, none of its children may be taken (they are adjacent to it). So dp[node][1] = w[node] + Σ dp[child][0] over all children.
If node is skipped, each child may independently do whatever is best for it. So dp[node][0] = Σ max(dp[child][0], dp[child][1]).

Why post-order. Each recurrence reads the children's dp values, so every child must be finished before its parent — left/right (or all children) first, then the node.

The answer. At the root there is no parent to constrain it, so either state is allowed: max(dp[root][0], dp[root][1]). Returning only dp[root][1] wrongly forces the root into the set.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

path 0-1-2 rooted at 0, weights = [4, 5, 4]

Interactive diagram

States on the path 0-1-2

node 2 (leaf)

Active call / nodeSupporting contextReturned stateNot active

Leaf 2 returns (0,4); node 1 returns (4,5); root 0 returns (5,8). Answer 8 = take ends 0 and 2.

Final result8

C · Code with teaching comments

solution.javaJava

Tree DP — Two States per Node (Optimal) — optimal

6 teaching notes

1
import java.util.*;
2
 
3
class TreeMIS {
4
    private List<List<Integer>> adj;
5
    private long[] w;
6
    private long[][] dp;   // dp[node][0]=skip, dp[node][1]=take
7
 
8
    long maxWeight(int n, int root, int[][] edges, long[] weights) {
9
        adj = new ArrayList<>();
10
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
11
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
12
        this.w = weights;
13
        // Two states per node: index 0 = skip this node, index 1 = take it.
14
        dp = new long[n][2];
15
 
16
        // Iterative post-order to avoid stack overflow on a chain of 10^5 nodes.
17
        int[] parent = new int[n];
18
        int[] order = new int[n];
19
        int idx = 0;
20
        Deque<Integer> stack = new ArrayDeque<>();
21
        boolean[] seen = new boolean[n];
22
        stack.push(root); parent[root] = root; seen[root] = true;
23
        while (!stack.isEmpty()) {            // BFS/DFS order for processing
24
            int node = stack.pop();
25
            order[idx++] = node;
26
            for (int next : adj.get(node)) {
27
                if (!seen[next]) { seen[next] = true; parent[next] = node; stack.push(next); }
28
            }
29
        }
30
        // Process children before parents: reverse discovery order works for a tree.
31
        // Reverse discovery order processes children before parents — an iterative
32
        // post-order.
33
        for (int i = n - 1; i >= 0; i--) {
34
            int node = order[i];
35
            long take = w[node];
36
            long skip = 0;
37
            for (int child : adj.get(node)) {
38
                // Skip the edge back to the parent so we only recurse into real
39
                // children.
40
                if (child == parent[node]) continue;
41
                // Taking node forbids each child → add the child's skip value.
42
                take += dp[child][0];
43
                // Skipping node frees each child → add the child's better option.
44
                skip += Math.max(dp[child][0], dp[child][1]);
45
            }
46
            dp[node][1] = take;
47
            dp[node][0] = skip;
48
        }
49
        // Root has no parent, so either state is allowed — take the max.
50
        return Math.max(dp[root][0], dp[root][1]);
51
    }
52
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.52 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7single node weight 5 — Leaf: take=5, skip=0 → max(0,5)=5.Explore edge cases

Edge cases handled

single node weight 5Leaf: take=5, skip=0 → max(0,5)=5.
all weights negativeEvery take is dominated by skip (0), so the answer is 0 — the empty set, which is valid.
star graph (center + many leaves)Either take the center (skip all leaves) or skip the center (take every positive leaf); the DP compares both.

Pitfalls

Using one state per node — you lose whether the node was taken, breaking the parent's recurrence.
Returning dp[root][1] instead of max(dp[root][0], dp[root][1]).
Recursing without a parent check — infinite loop over the parent edge on an undirected adjacency list.
Deep recursion on a chain of 10⁵ nodes — use an iterative post-order to avoid stack overflow.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class TreeMIS { private List<List<Integer>> adj; private long[] w;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

class TreeMIS {
    private List<List<Integer>> adj;
    private long[] w;
    private long[][] dp;   // dp[node][0]=skip, dp[node][1]=take

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

One state per node

Explore the code comparison

Don't write this

def dfs(node, parent):
    best = w[node]
    for c in children: best += dfs(c, node)   # single value, no skip case
    return best

Write this instead

def dfs(node, parent):
    take, skip = w[node], 0
    for c in children:
        ct, cs = dfs(c, node)            # (take, skip) for the child
        take += cs
        skip += max(ct, cs)
    return take, skip

Returning only the taken state

The root has no parent constraining it, so skipping the root can be better (e.g. a heavy node deep in the tree). Return the max of both root states.

Explore the code comparison

Don't write this

return dp[root][1];                 // forces the root into the set

Write this instead

return Math.max(dp[root][0], dp[root][1]);

No parent guard on an undirected tree

Adjacency lists store each edge in both directions. Without skipping the parent, the DFS revisits the parent as a 'child' and recurses forever.

Explore the code comparison

Don't write this

for child in adj[node]:
    dfs(child, node)               # also recurses into the parent

Write this instead

for child in adj[node]:
    if child == parent:
        continue
    dfs(child, node)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Post-order tree DP with two states per node: taken vs not taken

Code pattern to memorize

dfs(node, parent):
    take = weight[node]
    skip = 0
    for child != parent:
        dfs(child, node)
        take += dp[child][0]            # child must be skipped
        skip += max(dp[child][0], dp[child][1])  # child free to choose
    dp[node][1] = take
    dp[node][0] = skip

Rules to remember

1Two states per node: taken forces every child to the skipped state; skipped lets each child take its own max.
2Combine children independently — subtrees do not interact except through the parent's choice.
3Use post-order: a node's dp needs both children's dp values first.
4The answer is max(dp[root][0], dp[root][1]), not just dp[root][1].
5On a general (unrooted) tree, root it anywhere and pass the parent to avoid walking back up an edge.

Use this pattern when

Optimize over subsets of tree nodes with an adjacency (no-two-adjacent) constraint
House-Robber-style problems generalized from a line to a tree
Any 'select/skip with a local conflict' optimization on a tree
Counting or weighting where each node's choice only constrains its neighbors

Choose another pattern when

Graph has cycles (not a tree) → maximum independent set is NP-hard in general; tree DP relies on no cycles
Constraint spans non-adjacent nodes (e.g. distance ≤ 2) → states must encode more than taken/skipped
You need the actual set, not just its weight → store back-pointers / reconstruct after the DP
The line case (array, not tree) → 1-D House Robber DP is simpler

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

House Robber III
Coming soon
This exact DP on a binary tree — return (robbed, notRobbed) from each node.
House Robber
Coming soon
The line (path) special case: the same take/skip recurrence over an array.
Minimum Vertex Cover on a Tree
Coming soon
Complement view: minimum vertex cover = n − maximum independent set (unweighted) via the same DP.
Binary Tree Cameras
Coming soon
Three-state tree DP (covered/has-camera/uncovered) — same post-order combine, richer states.

Same pattern

←

Segment Tree for Range Sum

Continue · Next problem

Binary Search Tree: Insertion