Subtree DP

You Already Know This

If you've been following this course, you've been doing subtree DP since Chapter 1. Every time you wrote a postorder function that returns a value from children and combines it at the parent — that was subtree DP.

This lesson names the pattern formally and shows you how to think about it as dynamic programming. The DP table is the tree itself: one entry per node, and the value at each node is the answer for that node's subtree.

Subtree DP = postorder traversal + DP framing. The state is the node. The subproblems are the children's subtrees. The transition is the combine step.

---

The Formal View

In array DP, you have \(\text{dp}[i]\) and you fill it using \(\text{dp}[i-1]\), \(\text{dp}[i-2]\), etc. The dependency is index-based.

In subtree DP, you have \(\text{dp}[\text{node}]\) and you fill it using \(\text{dp}[\text{child}_1]\), \(\text{dp}[\text{child}_2]\), etc. The dependency is structural — it follows the tree edges.

The postorder traversal guarantees that every child is processed before its parent. This is the DP evaluation order. You don't need to worry about topological sort or memoization — the recursion handles it.

Array DP	Subtree DP
State: index \(i\)	State: node
Subproblems: \(\text{dp}[i-1]\), \(\text{dp}[i-2]\)	Subproblems: \(\text{dp}[\text{left}]\), \(\text{dp}[\text{right}]\)
Order: left to right	Order: postorder (leaves to root)
Base case: \(\text{dp}[0]\)	Base case: leaves or nullptr

---

Example: Subtree Sums

You've done this before: compute the sum of all values in each subtree.

          5
        /   \
       3     7
      / \     \
     1   4     6

\(\text{dp}[\text{node}]\) = sum of all values in the subtree rooted at node.

Node	Value	dp[left]	dp[right]	dp[node] = val + dp[left] + dp[right]
1	1	0	0	1
4	4	0	0	4
3	3	1	4	8
6	6	0	0	6
7	7	0	6	13
5	5	8	13	26

Nothing new here. But framing it as "fill a DP table indexed by nodes" makes the next problems easier to think about.

---

Example: Minimum Cost to Equalize Leaf Values

Problem: You have a binary tree where each node holds a positive integer. You can change any non-leaf node's value to any integer. The cost of a change is \(|\text{old value} - \text{new value}|\). Find the minimum total cost to make all leaf values equal.

Wait — you can't change leaf values. You can only change internal nodes. And the goal is to make all leaf values equal? That's already fixed by the input. If the leaves already have different values, you can't fix that by changing internal nodes.

That's a trick reading. The actual problem is different: make all leaf values equal by changing leaf values, where the cost is the sum of absolute changes. What target value minimizes total cost?

The target that minimizes \(\sum |x_i - t|\) is the median of the leaf values. So the subtree DP here collects all leaf values, finds the median, and computes the cost.

But the more interesting DP version: suppose you CAN change any node (including leaves), and the cost of changing node \(u\) from \(v_u\) to \(v_u'\) is \(|v_u - v_u'|\). Minimize total cost so that every parent equals the sum of its children.

DP state: \(\text{dp}[\text{node}]\) = minimum cost to make the subtree rooted at this node consistent (each parent = sum of children).

For a leaf: no children, no constraint. Cost = 0, and the subtree "output" is the leaf's value.

For an internal node: the children's subtrees produce their own sums. The node's natural value is its current value, but it "should" equal \(\text{leftSum} + \text{rightSum}\). The cost at this node is \(|\text{node.val} - (\text{leftSum} + \text{rightSum})|\).

---

Trace: Make Parent = Sum of Children

          5
        /   \
       3     7
      / \     \
     1   4     6

Process bottom-up. Each node returns (subtreeSum, totalCost).

Node	Value	leftSum	rightSum	expectedValue	cost at node	totalCost
1	1	—	—	1 (leaf)	0	0
4	4	—	—	4 (leaf)	0	0
3	3	1	4	1 + 4 = 5		3 - 5
6	6	—	—	6 (leaf)	0	0
7	7	—	6	0 + 6 = 6		7 - 6
5	5	5	6	5 + 6 = 11		5 - 11

Total minimum cost: 9.

After changes: node 3 becomes 5 (cost 2), node 7 becomes 6 (cost 1), node 5 becomes 11 (cost 6). Now 5's value (11) = left child (5) + right child (6). Node 3's value (5) = 1 + 4. Node 7's value (6) = 6. All consistent.

---

The Code

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

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

    bool isLeaf = (!root->left && !root->right);
    if (isLeaf) return {root->val, 0};

    auto [leftSum, leftCost] = solve(root->left);
    auto [rightSum, rightCost] = solve(root->right);

    int expectedValue = leftSum + rightSum;
    int costHere = abs(root->val - expectedValue);
    int totalCost = leftCost + rightCost + costHere;

    return {expectedValue, totalCost};
}

int minCostConsistent(TreeNode* root) {
    auto [subtreeSum, totalCost] = solve(root);
    return totalCost;
}

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(6);

    cout << minCostConsistent(root) << "\n";
    return 0;
}

Complexity: \(O(n)\) time, \(O(h)\) space.

---

Why "DP" and Not Just "Recursion"?

Fair question. The recursion and the DP are computing the same thing. So why introduce the DP framing?

Three reasons:

1. It connects tree problems to the DP problems you already know. House Robber on a list vs House Robber III on a tree — same DP, different structure. Seeing trees as DP tables makes this connection explicit.

2. It prepares you for rerooting (Lesson 3). Rerooting requires thinking about "what if the root were a different node?" — which is a DP state transformation. Without the DP lens, rerooting feels like a trick. With it, it's a natural extension.

3. It clarifies what's being memoized. In subtree DP, each node is computed exactly once. The call stack IS the memoization. When you move to iterative solutions (Chapter 10), you'll store these values explicitly.

Subtree DP is postorder with intent. You're not just traversing — you're filling a table where each entry depends on its children's entries.

---

Try It

Input: (the 6-node tree in main)
Output: 9

Predict before running: What if all internal nodes already equal the sum of their children? Then every cost is 0, and the answer is 0. That's the base case — the tree is already consistent.

Challenge: What if the constraint is "each parent equals the MAX of its children" instead of the sum? How does the DP change?

Challenge 2: What if you're allowed to change leaf values too, and you want to minimize total cost? Now the problem is harder because the leaf values aren't fixed.

Problems

Problem	Link	Difficulty
LC 508 — Most Frequent Subtree Sum	leetcode.com/problems/most-frequent-subtree-sum	Medium
LC 563 — Binary Tree Tilt	leetcode.com/problems/binary-tree-tilt	Easy
LC 1339 — Maximum Product of Splitted Binary Tree	leetcode.com/problems/maximum-product-of-splitted-binary-tree	Medium