DP on Trees
In this page:
Tree DP Idea
Tree DP solves a problem defined over a tree by computing an answer for each subtree, using the answers already computed for that subtree's children — so information flows upward from the leaves toward the root.
Example: Tree DP Idea
#include <iostream>
using namespace std;
int main() {
cout << "Tree DP: compute an answer for each subtree, information flows upward from leaves to root";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Tree DP: compute an answer for each subtree, information flows upward from leaves to root");
}
}print("Tree DP: compute an answer for each subtree, information flows upward from leaves to root")#include <stdio.h>
int main() {
printf("Tree DP: compute an answer for each subtree, information flows upward from leaves to root");
return 0;
}Login to try C/C++/Java code in the editor
Postorder DP
Because a node's answer typically depends on its children's answers, a postorder traversal (fully process every child before returning to the parent) is the natural way to compute tree DP: by the time you're ready to combine results at a node, every child result is already available.
Example: Postorder DP
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> children = {{1,2},{},{}};
int solve(int node) {
int total = 0;
for (int c : children[node]) total += solve(c);
return total + 1;
}
int main() { cout << "Subtree size at root (children fully processed first): " << solve(0); return 0; }import java.util.*;
public class Main {
static List<List<Integer>> children = Arrays.asList(Arrays.asList(1,2), Arrays.asList(), Arrays.asList());
static int solve(int node) {
int total = 0;
for (int c : children.get(node)) total += solve(c);
return total + 1;
}
public static void main(String[] args) { System.out.println("Subtree size at root (children fully processed first): " + solve(0)); }
}children = [[1,2],[],[]]
def solve(node):
return sum(solve(c) for c in children[node]) + 1
print("Subtree size at root (children fully processed first):", solve(0))#include <stdio.h>
int children[3][2] = {{1,2},{-1,-1},{-1,-1}};
int solve(int node) {
int total = 0;
for (int i = 0; i < 2; i++) if (children[node][i] != -1) total += solve(children[node][i]);
return total + 1;
}
int main() { printf("Subtree size at root (children fully processed first): %d", solve(0)); return 0; }Login to try C/C++/Java code in the editor
Choose or Skip
Some tree DP problems, like the tree version of House Robber, must decide at each node whether to take that node (and therefore skip its immediate children) or skip it (allowing children to be freely taken), and the DP tracks both possibilities separately.
Example: Choose or Skip
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> children = {{1,2},{},{}};
int val[3] = {5, 3, 4};
int solveTaken(int node);
int solveSkipped(int node);
int solveTaken(int node) {
int sum = val[node];
for (int c : children[node]) sum += solveSkipped(c);
return sum;
}
int solveSkipped(int node) {
int sum = 0;
for (int c : children[node]) sum += max(solveTaken(c), solveSkipped(c));
return sum;
}
int main() { cout << "House Robber on a tree, best at root: " << max(solveTaken(0), solveSkipped(0)); return 0; }import java.util.*;
public class Main {
static List<List<Integer>> children = Arrays.asList(Arrays.asList(1,2), Arrays.asList(), Arrays.asList());
static int[] val = {5, 3, 4};
static int solveTaken(int node) {
int sum = val[node];
for (int c : children.get(node)) sum += solveSkipped(c);
return sum;
}
static int solveSkipped(int node) {
int sum = 0;
for (int c : children.get(node)) sum += Math.max(solveTaken(c), solveSkipped(c));
return sum;
}
public static void main(String[] args) { System.out.println("House Robber on a tree, best at root: " + Math.max(solveTaken(0), solveSkipped(0))); }
}children = [[1,2],[],[]]
val = [5, 3, 4]
def solve_taken(node):
return val[node] + sum(solve_skipped(c) for c in children[node])
def solve_skipped(node):
return sum(max(solve_taken(c), solve_skipped(c)) for c in children[node])
print("House Robber on a tree, best at root:", max(solve_taken(0), solve_skipped(0)))#include <stdio.h>
int children[3][2] = {{1,2},{-1,-1},{-1,-1}};
int val[3] = {5, 3, 4};
int solveTaken(int node);
int solveSkipped(int node);
int solveTaken(int node) {
int sum = val[node];
for (int i = 0; i < 2; i++) if (children[node][i] != -1) sum += solveSkipped(children[node][i]);
return sum;
}
int solveSkipped(int node) {
int sum = 0;
for (int i = 0; i < 2; i++) if (children[node][i] != -1) {
int c = children[node][i];
int t = solveTaken(c), s = solveSkipped(c);
sum += t > s ? t : s;
}
return sum;
}
int main() {
int t = solveTaken(0), s = solveSkipped(0);
printf("House Robber on a tree, best at root: %d", t > s ? t : s);
return 0;
}Login to try C/C++/Java code in the editor
Tree States
Because a node's best answer can differ depending on whether it was selected or not, many tree DP problems store two values per node instead of one — for example dp[node][0] for 'not taken' and dp[node][1] for taken — and combine them differently when merging into the parent.
Example: Tree States
#include <iostream>
using namespace std;
int main() {
int dpTaken = 5, dpNotTaken = 7;
cout << "Two values stored per node: dp[node][0]=not taken=" << dpNotTaken << ", dp[node][1]=taken=" << dpTaken;
return 0;
}public class Main {
public static void main(String[] args) {
int dpTaken = 5, dpNotTaken = 7;
System.out.println("Two values stored per node: dp[node][0]=not taken=" + dpNotTaken + ", dp[node][1]=taken=" + dpTaken);
}
}dp_taken, dp_not_taken = 5, 7
print(f"Two values stored per node: dp[node][0]=not taken={dp_not_taken}, dp[node][1]=taken={dp_taken}")#include <stdio.h>
int main() {
int dpTaken = 5, dpNotTaken = 7;
printf("Two values stored per node: dp[node][0]=not taken=%d, dp[node][1]=taken=%d", dpNotTaken, dpTaken);
return 0;
}Login to try C/C++/Java code in the editor
Practice
Tree DP combines three ideas at once: recursion to walk the structure, subtree boundaries to define each subproblem, and stored per-node states to avoid recomputing the same subtree's answer more than once.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Tree DP = recursion + subtree boundaries + stored per-node states to avoid recomputation";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Tree DP = recursion + subtree boundaries + stored per-node states to avoid recomputation");
}
}print("Tree DP = recursion + subtree boundaries + stored per-node states to avoid recomputation")#include <stdio.h>
int main() {
printf("Tree DP = recursion + subtree boundaries + stored per-node states to avoid recomputation");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 12 topics to unlock
0/12 topics done
Complete these topics first: