Dynamic Programming • Trees

Tree DP Basics

Learn how to aggregate data efficiently across a tree structure using Depth-First Search (DFS) and post-order traversal.

Try Interactive Simulator

Overview

Tree DP is just DP where the "graph" of states is a tree. Since trees don't have cycles, we don't need a `visited` array, just a `parent` pointer to avoid going backward.

Post-Order Magic

Most Tree DP problems use Post-Order Traversal. You visit the children, get their answers, and then use those answers to compute the parent's answer.

The DP State

Usually, `dp[u]` represents the answer for the subtree rooted at node `u`. For example, `dp[u]` could be the maximum path sum in that subtree.

Global vs Local

Often, the function returns a local answer to help the parent, but updates a global variable (like `max_path`) during the process, since the best path might not go through the ultimate root.

0

1

2

3

4

Code Tracker

:::

1function dfs(node, parent) {

2 let size = 1; // Count itself

3 for (let child of adj[node]) {

4 if (child !== parent) {

5 size += dfs(child, node);

6 }

7 }

8 dp[node] = size;

9 return size;

10}

Tree Dp Basics

Tree Dp Basics

Tree DP Basics

Overview

Post-Order Magic

The DP State

Global vs Local

Tree DP Basics

Overview

Post-Order Magic

The DP State

Global vs Local