๐ Why This Pattern?
Some tree problems are not solvable by simple traversals.
They require optimal substructure (like DP on arrays/graphs), where each nodeโs solution depends on its childrenโs solutions.
Typical cases:
- Maximize/minimize some property.
- Choose/donโt choose a node (like knapsack on a tree).
- Path-based optimizations.
๐ Core Idea (Template)
Tree DP = DFS + store results of children + combine for parent.
Pseudocode:
function dfs(node):
if node == null:
return baseCase
left = dfs(node.left)
right = dfs(node.right)
return combine(node, left, right)
โ Classic Problems
1. Diameter of Binary Tree (LeetCode 543)
Longest path between any two nodes.
class Solution {
int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
height(root);
return diameter;
}
private int height(TreeNode node) {
if (node == null) return 0;
int left = height(node.left);
int right = height(node.right);
diameter = Math.max(diameter, left + right);
return 1 + Math.max(left, right);
}
}
Pattern: Height DP + global max.
2. House Robber III (LeetCode 337)
Choose nodes such that no two directly-linked nodes are chosen.
class Solution {
public int rob(TreeNode root) {
int[] res = dfs(root);
return Math.max(res[0], res[1]);
}
private int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0};
int[] left = dfs(node.left);
int[] right = dfs(node.right);
// res[0] = max if NOT robbing this node
// res[1] = max if robbing this node
int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
int rob = node.val + left[0] + right[0];
return new int[]{notRob, rob};
}
}
Pattern: Two states per node (rob/not rob).
3. Maximum Path Sum (LeetCode 124)
Find maximum sum of any path (may pass through root).
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return maxSum;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = Math.max(0, dfs(node.left));
int right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, node.val + left + right);
return node.val + Math.max(left, right);
}
}
Pattern: Max gain from child + track global best.
4. Longest Zigzag Path in a Binary Tree (LeetCode 1372)
class Solution {
int maxLen = 0;
public int longestZigZag(TreeNode root) {
dfs(root, true, 0);
dfs(root, false, 0);
return maxLen;
}
private void dfs(TreeNode node, boolean isLeft, int length) {
if (node == null) return;
maxLen = Math.max(maxLen, length);
if (isLeft) {
dfs(node.left, false, length + 1);
dfs(node.right, true, 1);
} else {
dfs(node.right, true, length + 1);
dfs(node.left, false, 1);
}
}
}
Pattern: DP with direction state.
5. Count Good Nodes in Binary Tree (LeetCode 1448)
A node is "good" if itโs >= max on the path from root.
class Solution {
public int goodNodes(TreeNode root) {
return dfs(root, root.val);
}
private int dfs(TreeNode node, int maxSoFar) {
if (node == null) return 0;
int good = (node.val >= maxSoFar) ? 1 : 0;
maxSoFar = Math.max(maxSoFar, node.val);
return good + dfs(node.left, maxSoFar) + dfs(node.right, maxSoFar);
}
}
Pattern: DP with path-state (max so far).
๐ Advanced Variations
- Minimum Vertex Cover on Tree (classic DP): choose minimum nodes such that every edge is covered.
- Tree Coloring DP: assign colors with constraints (used in graph + tree DP).
- Binary Tree Cameras (LeetCode 968): place cameras to cover all nodes (3-state DP).
๐ฏ Quick Pattern Checklist
- โ Global property (diameter, max path) โ compute from children + update global.
- โ Choice-based (rob/not rob) โ DP with multiple states per node.
- โ Path-based constraints (good nodes, zigzag) โ pass down state.
- โ Optimization (min/max) โ combine childrenโs results carefully.
๐ฅ Key Takeaway:
Tree DP = DFS + memoization of childrenโs results.
Each node โ small decision problem โ combine โ solve big problem.
Top comments (0)