DP on Binary Trees
You'll learn how to solve optimization problems on binary trees by defining dynamic programming states at each node that combine information from its left and right subtrees.
The Core Idea
In DP on binary trees, you recursively compute optimal solutions for each node by:
- Solving the problem for the left subtree
- Solving the problem for the right subtree
- Combining those results at the current node based on your problem's requirements
The state at each node typically tracks different scenarios (like "include this node" vs "exclude this node") and merges the best outcomes from both children.
How It Works
Think of it like calculating a company's total value. Each department (node) reports two numbers to its manager: "value if we participate in the project" and "value if we don't." The manager combines these reports from both teams below them, adds their own contribution, and passes it upward. The CEO at the root makes the final decision based on all aggregated information.
Binary tree specificity: Unlike general trees, each node has at most two children, simplifying your state transitions—you only combine left and right results.
Typical Pattern
For each node, you might track:
- Best result including this node
- Best result excluding this node
Then recursively:
result[node] = combine(result[left_child], result[right_child], node.value)
The base case is always the leaf nodes (or null children), where you return simple initial values.
Common Applications
- Maximum path sum in a binary tree
- House robber on trees (can't pick adjacent nodes)
- Binary tree cameras placement
- Vertex cover on binary trees
Key Takeaway: DP on binary trees leverages the natural recursive structure of trees, defining states at each node that intelligently merge left and right subtree solutions to build the global optimum.