DP on Trees
Dynamic programming on trees involves solving problems on tree data structures, often using DFS and recursion. The DP state is usually defined for each node, and we combine results from children.
Example: Maximum Sum Path in Binary Tree (no root-to-leaf restriction) – we compute the maximum path sum that can be obtained from any node to any node. For each node, we compute the maximum path sum that goes through that node and update global maximum.
Simpler: Diameter of a tree (longest path between any two nodes). We compute for each node the height of left and right subtrees, and update diameter as left + right.
Java code for tree diameter (DP on tree):
int diameter = 0;
public int heightAndDiameter(TreeNode root) {
if (root == null) return 0;
int left = heightAndDiameter(root.left);
int right = heightAndDiameter(root.right);
diameter = Math.max(diameter, left + right);
return Math.max(left, right) + 1;
}
Tree DP is used in problems like largest independent set, tree matching, etc.
Two Minute Drill
- Tree DP uses DFS to compute values for nodes based on children.
- State often involves whether a node is selected or not.
- Diameter of tree is classic DP on tree problem.
- Complexity O(n) for tree DP.
Need more clarification?
Drop us an email at career@quipoinfotech.com