DP on Trees
Software Engineer path · lesson 39 of 99Tree Dynamic Programming applies DP bottom-up through a rooted tree, processing children before parents in a post-order DFS so each subtree is solved exactly once. Because trees are acyclic, there are no overlapping subproblems across branches — each child's result is computed once and aggregated upward to its parent. Classic problems include finding the tree diameter, the maximum path sum (where a path can branch through a node), and the maximum weight independent set (where chosen nodes cannot be adjacent). This visualization animates the Maximum Path Sum algorithm on a five-node binary tree, showing how each node separately tracks the best downward path to return to its parent and the best full path through itself that updates the global answer.
Up to 15 slots (4 levels), numbers −99 to 99; children of slot i are 2i+1 and 2i+2.
Solve children before parents (post-order). Each node reports its best downward path.
- 1solve(node): # post-order: children first
- 2 if node is empty: return 0
- 3 L = max(0, solve(left)); R = max(0, solve(right)) # drop negative branches
- 4 best = max(best, node.val + L + R) # path that bends here
- 5 return node.val + max(L, R) # path that continues up
- Nodes solved
- 0 / 5
Best so far: —
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Maximum independent set on a tree
Order the steps of the take/skip tree DP.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
Test your knowledge
In "Binary Tree Maximum Path Sum", why must we return a different value than we update?
The short version
Imagine a company org chart. To calculate the total bonus pool, each manager sums their team's bonuses and passes the total up. DP on trees computes values bottom-up from leaves to root.
In more depth
Bottom-Up Aggregation
Tree DP processes nodes in post-order: handle children first, then compute parent's value.
Common Pattern:
def dfs(node):
if not node: return base_case
left = dfs(node.left)
right = dfs(node.right)
# Update global answer using both subtrees
global_ans = max(global_ans, f(left, right, node))
# Return single-path value to parent
return g(left, right, node)Path vs Subtree:
Rerooting:
For "answer rooted at each node", compute once from a root, then propagate to children using parent info.
Key Gotchas:
When to reach for this
- Find maximum/minimum value involving tree paths
- Aggregate values from subtrees
- Each node makes a choice based on children
- Keywords: 'path in tree', 'subtree sum', 'tree diameter'
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required