Course contentsShow
← Computer Science
Lesson 945 of 2,87222. Dynamic ProgrammingFree lesson

Maximum Independent Set on Trees

Finding the largest set of non-adjacent nodes in a tree using DP on subtrees.

Maximum Independent Set on Trees

You'll learn how to find the largest set of tree nodes where no two are adjacent using dynamic programming on subtrees.

The Core Idea

Imagine you're organizing a family reunion but some relatives can't stand each other—specifically, parents and children refuse to attend together. You want to invite the maximum number of people. This is the Maximum Independent Set problem: selecting the most nodes from a tree such that no two selected nodes share an edge.

The key insight is that for each node, you have two choices:

  1. Include it — then you cannot include its children
  2. Exclude it — then you can freely choose to include or exclude each child

Building the DP Solution

Define your state for each node:

  • dp[node][0] = maximum independent set in the subtree rooted at node, excluding node
  • dp[node][1] = maximum independent set in the subtree rooted at node, including node

The recurrence works bottom-up from leaves:

dp[node][0] = sum of max(dp[child][0], dp[child][1]) for all children
dp[node][1] = 1 + sum of dp[child][0] for all children

When you exclude a node, you can take the better choice (include or exclude) for each child. When you include a node, you must exclude all direct children but gain +1.

The answer is max(dp[root][0], dp[root][1]).

This works because subtrees are independent—your decision for one subtree doesn't affect another except through their common parent, which we handle in the recurrence.

Key Takeaway: Maximum Independent Set on trees uses bottom-up DP where each node's optimal solution depends only on whether it's included and the best solutions from its children's subtrees.