Tree DP is the dynamic-programming pattern for aggregating optimal answers over rooted subtrees. Strong candidates explain what each subtree state means before writing DFS, because tree DP is easy to code incorrectly when the child-to-parent contract is unclear.
Interview lens
A strong explanation should name the invariant, the safe transition, and the condition that makes this pattern preferable to brute force.
Pattern Summary Table
| Pattern | When to Use | Key Idea | Example |
|---|---|---|---|
| 04 27 Tree Dp Pattern | the problem is on a tree and each node answer depends on child subtree answers | run DFS and return a well-defined DP state from each subtree | House Robber III |
Problem Statement
Given a tree-structured problem, compute an answer where each node combines information from its children without introducing cycles.
Note
Emphasize the constraints before coding. The real signal is often whether the brute-force search space, update volume, or graph model makes the naive solution impossible.
Pattern Recognition Signals
- Keywords in the problem: tree DP, subtree state, rerooting, post-order aggregation.
- Structural signal: each subtree can be solved independently once the parent-child direction is fixed.
- Complexity signal: the optimized version avoids repeated rescans, recomputation, or state explosion that brute force would suffer.
Important
If the graph is a tree and each answer is built from child subtrees, think tree DP.
Java Template
int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0};
int[] L = dfs(node.left), R = dfs(node.right);
int take = node.val + L[1] + R[1];
int skip = Math.max(L[0], L[1]) + Math.max(R[0], R[1]);
return new int[]{take, skip};
}
Dry Run (House Robber III Style)
Interpretation:
- return
[take, skip] take: max if current node is robbedskip: max if current node is not robbed
For node value 3 with children results:
- left
[4,2], right[1,5] take = 3 + 2 + 5 = 10skip = max(4,2) + max(1,5) = 9
Node contributes [10,9] upward.
This post-order combination is the core Tree-DP pattern.
Rooting and Parent Tracking (General Trees)
For non-binary trees, pass parent to avoid revisiting:
void dfs(int u, int parent) {
for (int v : g.get(u)) {
if (v == parent) continue;
dfs(v, u);
}
}
Tree-DP on adjacency-list trees depends on this parent exclusion.
Debug Checklist
- print DP state per node after combining children
- verify leaf/base state matches recurrence
- ensure each edge processed once (tree, not cyclic traversal)
Most tree-DP bugs are wrong state meaning or combine formulas.
Problem 1: House Robber III
Problem description: Given a binary tree of house values, return the maximum amount you can rob without robbing both a node and its direct child.
What we are solving actually: Each node has two coupled outcomes: take it or skip it. Tree DP works because a parent only needs the two summarized states from each child, not every full subtree configuration.
What we are doing actually:
- Run post-order DFS so children are solved before the parent.
- Return two values for every node:
takeandskip. - If we take the node, children must be skipped.
- If we skip the node, each child chooses its own better option.
public int rob(TreeNode root) {
int[] state = dfs(root);
return Math.max(state[0], state[1]);
}
private int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0};
int[] left = dfs(node.left);
int[] right = dfs(node.right);
int take = node.val + left[1] + right[1]; // Taking this node forces both children into their skip state.
int skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // Skipping lets each child choose its better outcome.
return new int[]{take, skip};
}
Debug steps:
- print each node’s returned
[take, skip]pair after DFS combines its children - test a leaf-only tree and a chain-shaped tree to catch base-case mistakes
- verify the invariant that a node’s result depends only on already-computed child states
Problem-Fit Checklist
- Identify whether input size or query count requires preprocessing or specialized data structures.
- Confirm problem constraints (sorted input, non-negative weights, DAG-only, immutable array, etc.).
- Validate that the pattern gives asymptotic improvement over brute-force under worst-case input.
- Define explicit success criteria: value only, index recovery, count, path reconstruction, or ordering.
Invariant and Reasoning
- Write one invariant that must stay true after every transition (loop step, recursion return, or update).
- Ensure each step makes measurable progress toward termination.
- Guard boundary states explicitly (empty input, singleton, duplicates, overflow, disconnected graph).
- Add a quick correctness check using a tiny hand-worked example before coding full solution.
Complexity and Design Notes
- Compute time complexity for both preprocessing and per-query/per-update operations.
- Track memory overhead and object allocations, not only Big-O notation.
- Prefer primitives and tight loops in hot paths to reduce GC pressure in Java.
- If multiple variants exist, choose the one with the simplest correctness proof first.
Production Perspective
- Convert algorithmic states into explicit metrics (queue size, active nodes, cache hit ratio, relaxation count).
- Add guardrails for pathological inputs to avoid latency spikes.
- Keep implementation deterministic where possible to simplify debugging and incident analysis.
- Separate pure algorithm logic from I/O and parsing so the core stays testable.
Implementation Workflow
- Implement the minimal correct template with clear invariants.
- Add edge-case tests before optimizing.
- Measure complexity-sensitive operations on realistic input sizes.
- Refactor for readability only after behavior is locked by tests.
Common Mistakes
- Choosing the pattern without proving problem fit.
- Ignoring edge cases (empty input, duplicates, overflow, disconnected state).
- Mixing multiple strategies without clear invariants.
- No complexity analysis against worst-case input.
Practice Set (Recommended Order)
Key Takeaways
- This pattern is most effective when transitions are explicit and invariants are enforced at every step.
- Strong preconditions and boundary handling make these implementations production-safe.
- Reuse this template and adapt it per problem constraints.
Categories
Tags