Pattern 6: DP on Trees Problems

The Hierarchical Pattern: State is dp[node] or dp[node][state] = answer for subtree rooted at node. DFS/post-order traversal to combine children's solutions.

The Core Pattern

THE MENTAL MODEL

Imagine you're evaluating a company's organizational hierarchy:

Start with leaf employees (no subordinates)
Compute their individual contribution
Move up: each manager's value = their contribution + combined team value
Process bottom-up (can't evaluate a manager until you've evaluated their team)
The CEO's value is computed last, using all subordinates' values

This is Tree DP.

Pattern Recognition

WHEN YOU SEE THIS PATTERN

Keywords: "tree", "subtree", "binary tree", "path in tree", "ancestor", "for each node"

Structure:

Hierarchical structure (tree)
Answer for a node depends on children's answers
Need to combine information from left and right subtrees

State:

dp[node] = "answer for subtree rooted at node"
OR dp[node][state] = "answer when node is in specific state"

Traversal: DFS (usually post-order) - children before parent

Combine: Merge children's solutions to get parent's solution

Category 1: Core Tree DP Problems

1. House Robber III (LC 337)

PROBLEM

The thief has found himself a new place to rob - a binary tree. Each node has a certain amount of money.

Constraint: Two directly-linked houses cannot be robbed on the same night.

Return the maximum amount of money the thief can rob without alerting the police.

State Definition:

dp[node][0] = max money from subtree when node is NOT robbed
dp[node][1] = max money from subtree when node IS robbed

Transition:

If rob node: can't rob children
  dp[node][1] = node.val + dp[left][0] + dp[right][0]

If don't rob node: can choose whether to rob children
  dp[node][0] = max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1])

class Solution {
    public int rob(TreeNode root) {
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }

    // Returns [not_robbed, robbed]
    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }

        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        // Don't rob this node: can rob or not rob children
        int notRobbed = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        // Rob this node: can't rob children
        int robbed = node.val + left[0] + right[0];

        return new int[]{notRobbed, robbed};
    }
}

THE CANONICAL TREE DP PROBLEM

Classic state machine on a tree:

Two states per node (rob/don't rob)
Constraint enforced through state transitions
Post-order: compute children before parent

Pattern: Return tuple of states, combine at parent

2. Binary Tree Maximum Path Sum (LC 124)

PROBLEM

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge. A node can only appear once.

The path sum is the sum of node values in the path.

Return the maximum path sum of any non-empty path.

State Definition:

dp[node] = max path sum extending downward from node
global_max = max path sum in entire tree (may go through node)

Key Insight: Path through node = node.val + left_contribution + right_contribution

class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) return 0;

        // Recursively get max gain from children
        // Use max(0, gain) to ignore negative contributions
        int leftGain = Math.max(0, maxGain(node.left));
        int rightGain = Math.max(0, maxGain(node.right));

        // Path through this node
        int pathThroughNode = node.val + leftGain + rightGain;

        // Update global maximum
        maxSum = Math.max(maxSum, pathThroughNode);

        // Return max gain extending from this node upward
        return node.val + Math.max(leftGain, rightGain);
    }
}

CRITICAL DISTINCTION

What we return: Max path extending downward (one branch) What we track globally: Max path anywhere (can use both branches)

       10
      /  \
     2    10
    / \     \
   20  1   -25
                \
                  3   4

Return upward: 10 + max(left, right) = one branch
Global max: 10 + left + right = through node (both branches)

3. Diameter of Binary Tree (LC 543)

PROBLEM

The diameter of a binary tree is the length of the longest path between any two nodes. The path may or may not pass through the root.

The length is the number of edges.

State Definition:

dp[node] = max depth from this node downward
global_max_diameter = max diameter seen

Key: Diameter through node = left_depth + right_depth

class Solution {
    int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return diameter;
    }

    private int depth(TreeNode node) {
        if (node == null) return 0;

        int leftDepth = depth(node.left);
        int rightDepth = depth(node.right);

        // Diameter through this node
        diameter = Math.max(diameter, leftDepth + rightDepth);

        // Return depth for use by parent
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

SIMILAR TO MAX PATH SUM

Pattern:

Return: single-branch metric (depth, gain)
Track globally: combined metric (diameter, path sum)

Formula: through_node = left_metric + right_metric

4. Longest Univalue Path (LC 687)

State Definition:

dp[node] = longest univalue path ending at this node
Track global max

Transition: If child has same value, can extend path

class Solution {
    int maxPath = 0;

    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return maxPath;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;

        int left = dfs(node.left);
        int right = dfs(node.right);

        int leftPath = 0, rightPath = 0;

        // Extend if children have same value
        if (node.left != null && node.left.val == node.val) {
            leftPath = left + 1;
        }
        if (node.right != null && node.right.val == node.val) {
            rightPath = right + 1;
        }

        // Path through this node
        maxPath = Math.max(maxPath, leftPath + rightPath);

        // Return single path for parent
        return Math.max(leftPath, rightPath);
    }
}

5. Binary Tree Cameras (LC 968)

PROBLEM

You are given the root of a binary tree. Install cameras on tree nodes. Each camera can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes.

State Definition:

State 0: Covered by child's camera
State 1: Has camera
State 2: Not covered (needs coverage)

Greedy Strategy: Place cameras as low as possible

class Solution {
    int cameras = 0;

    public int minCameraCover(TreeNode root) {
        // If root is not covered, place camera at root
        if (dfs(root) == 2) cameras++;
        return cameras;
    }

    // Returns: 0 = covered, 1 = has camera, 2 = not covered
    private int dfs(TreeNode node) {
        if (node == null) return 0;  // null is "covered"

        int left = dfs(node.left);
        int right = dfs(node.right);

        // If either child is not covered, place camera here
        if (left == 2 || right == 2) {
            cameras++;
            return 1;
        }

        // If either child has camera, this node is covered
        if (left == 1 || right == 1) {
            return 0;
        }

        // Both children are covered but don't have cameras
        // This node is not covered
        return 2;
    }
}

GREEDY + DP

This is a greedy strategy implemented with tree DP:

Post-order traversal ensures we process children first
Greedy: place camera as low as possible
Three states track coverage status

Key: null is considered "covered" to allow leaf cameras to cover parents

Category 2: Subtree Properties

6. Count Univalue Subtrees (LC 250)

State Definition:

dp[node] = is subtree rooted at node uniform?
Count uniform subtrees globally

Transition: Uniform if children are uniform AND all values match

class Solution {
    int count = 0;

    public int countUnivalSubtrees(TreeNode root) {
        isUnival(root);
        return count;
    }

    private boolean isUnival(TreeNode node) {
        if (node == null) return true;

        boolean leftUnival = isUnival(node.left);
        boolean rightUnival = isUnival(node.right);

        // Check if this subtree is uniform
        if (leftUnival && rightUnival) {
            if ((node.left == null || node.left.val == node.val) &&
                (node.right == null || node.right.val == node.val)) {
                count++;
                return true;
            }
        }

        return false;
    }
}

7. Largest BST Subtree (LC 333)

State Definition: Return tuple (isBST, size, min, max)

Transition: Check BST property using children's min/max

class Solution {
    int maxSize = 0;

    public int largestBSTSubtree(TreeNode root) {
        dfs(root);
        return maxSize;
    }

    // Returns [isBST, size, min, max]
    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{1, 0, Integer.MAX_VALUE, Integer.MIN_VALUE};
        }

        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        // Check if current subtree is BST
        if (left[0] == 1 && right[0] == 1 &&
            node.val > left[3] && node.val < right[2]) {

            int size = left[1] + right[1] + 1;
            maxSize = Math.max(maxSize, size);

            int min = node.left != null ? left[2] : node.val;
            int max = node.right != null ? right[3] : node.val;

            return new int[]{1, size, min, max};
        }

        // Not a BST
        return new int[]{0, 0, 0, 0};
    }
}

MULTI-VALUE RETURN

Common pattern: Return tuple of values needed by parent:

Boolean: is property satisfied?
Size/count: metric for this subtree
Min/max: boundary values for validation

Parent uses these to compute its own values

8. Most Frequent Subtree Sum (LC 508)

State Definition: dp[node] = sum of subtree

Goal: Count frequency of each sum

class Solution {
    Map<Integer, Integer> sumCount = new HashMap<>();
    int maxFrequency = 0;

    public int[] findFrequentTreeSum(TreeNode root) {
        subtreeSum(root);

        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : sumCount.entrySet()) {
            if (entry.getValue() == maxFrequency) {
                result.add(entry.getKey());
            }
        }

        return result.stream().mapToInt(i -> i).toArray();
    }

    private int subtreeSum(TreeNode node) {
        if (node == null) return 0;

        int leftSum = subtreeSum(node.left);
        int rightSum = subtreeSum(node.right);

        int sum = node.val + leftSum + rightSum;

        sumCount.put(sum, sumCount.getOrDefault(sum, 0) + 1);
        maxFrequency = Math.max(maxFrequency, sumCount.get(sum));

        return sum;
    }
}

9. Distribute Coins in Binary Tree (LC 979)

PROBLEM

You are given the root of a binary tree with n nodes. Each node has some number of coins. There are n coins in total.

In one move, we can choose two adjacent nodes and move one coin from one to the other. Find the minimum number of moves required to make every node have exactly one coin.

State Definition: dp[node] = excess/deficit of coins in subtree

Positive = excess coins
Negative = needs coins

Key Insight: Moves = sum of |excess/deficit| for all subtrees

class Solution {
    int moves = 0;

    public int distributeCoins(TreeNode root) {
        dfs(root);
        return moves;
    }

    // Returns excess (+) or deficit (-) coins in subtree
    private int dfs(TreeNode node) {
        if (node == null) return 0;

        int leftBalance = dfs(node.left);
        int rightBalance = dfs(node.right);

        // This subtree's balance: coins - nodes
        int balance = node.val + leftBalance + rightBalance - 1;

        // Each coin moved contributes to move count
        moves += Math.abs(leftBalance) + Math.abs(rightBalance);

        return balance;
    }
}

BALANCE/FLOW PATTERN

Pattern: Compute excess or deficit at each node

Positive: have extra
Negative: need more
Moves = total absolute flow

Formula: balance = coins - 1 (for self) + children_balance

10. Sum of Distances in Tree (LC 834)

PROBLEM

You have an undirected tree with n nodes labeled from 0 to n-1. Return an array answer where answer[i] is the sum of distances between node i and all other nodes.

Two-Pass Re-rooting Technique:

Pass 1: Compute for root

count[node] = number of nodes in subtree
dist[node] = sum of distances to all nodes in subtree

Pass 2: Re-root to compute for all nodes

Use parent's answer to compute child's answer

class Solution {
    int[] answer;
    int[] count;  // count[i] = size of subtree i
    List<Integer>[] graph;
    int n;

    public int[] sumOfDistancesInTree(int n, int[][] edges) {
        this.n = n;
        graph = new ArrayList[n];
        answer = new int[n];
        count = new int[n];

        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        // Pass 1: compute for root
        dfs1(0, -1);
        // Pass 2: re-root
        dfs2(0, -1);

        return answer;
    }

    // Pass 1: count nodes and distances in subtree
    private void dfs1(int node, int parent) {
        count[node] = 1;
        for (int child : graph[node]) {
            if (child == parent) continue;
            dfs1(child, node);

            count[node] += count[child];
            answer[node] += answer[child] + count[child];
        }
    }

    // Pass 2: re-root using parent's answer
    private void dfs2(int node, int parent) {
        for (int child : graph[node]) {
            if (child == parent) continue;

            // Re-root from node to child
            // Nodes in child's subtree get closer by 1
            // Other nodes get farther by 1
            answer[child] = answer[node] - count[child] + (n - count[child]);

            dfs2(child, node);
        }
    }
}

ADVANCED: RE-ROOTING TECHNIQUE

Two-pass strategy:

Pass 1 (bottom-up): Compute answer for root

Process subtrees, aggregate up

Pass 2 (top-down): Use parent's answer to compute children

Adjust for change in root

Formula: When moving root from parent to child:

answer[child] = answer[parent]
                - count[child]      // these get closer
                + (n - count[child]) // these get farther

Category 3: Path/Distance Problems

11. Maximum Difference Between Node and Ancestor (LC 1026)

State Definition: Track (min, max) along path from root

Return: Max difference seen

class Solution {
    public int maxAncestorDiff(TreeNode root) {
        return dfs(root, root.val, root.val);
    }

    private int dfs(TreeNode node, int min, int max) {
        if (node == null) {
            return max - min;
        }

        min = Math.min(min, node.val);
        max = Math.max(max, node.val);

        int leftDiff = dfs(node.left, min, max);
        int rightDiff = dfs(node.right, min, max);

        return Math.max(leftDiff, rightDiff);
    }
}

TOP-DOWN PATTERN

Unlike post-order, this is top-down (pre-order):

Pass information from parent to children
Track path state as we descend

Use case: When answer depends on ancestors, not descendants

12. Longest ZigZag Path in Binary Tree (LC 1372)

State Definition:

dp[node][0] = longest zigzag ending here going left
dp[node][1] = longest zigzag ending here going right

Zigzag rule: left → right → left → right...

class Solution {
    int maxLength = 0;

    public int longestZigZag(TreeNode root) {
        dfs(root);
        return maxLength;
    }

    // Returns [left_length, right_length]
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{-1, -1};

        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        // Zigzag going left: came from right child going left
        int leftZigzag = left[1] + 1;

        // Zigzag going right: came from left child going right
        int rightZigzag = right[0] + 1;

        maxLength = Math.max(maxLength, Math.max(leftZigzag, rightZigzag));

        return new int[]{leftZigzag, rightZigzag};
    }
}

DIRECTION-BASED STATE

Two states: came from left vs came from right

Transition: Alternate direction to continue zigzag

Pattern: State encodes how we arrived at this node

13. Number of Good Leaf Nodes Pairs (LC 1530)

State Definition: dp[node] = list of distances to all leaves in subtree

Goal: Count pairs of leaves within distance d

class Solution {
    int result = 0;

    public int countPairs(TreeNode root, int distance) {
        dfs(root, distance);
        return result;
    }

    // Returns list of distances to leaves in subtree
    private List<Integer> dfs(TreeNode node, int distance) {
        if (node == null) return new ArrayList<>();

        if (node.left == null && node.right == null) {
            List<Integer> list = new ArrayList<>();
            list.add(1);  // distance to this leaf is 1
            return list;
        }

        List<Integer> left = dfs(node.left, distance);
        List<Integer> right = dfs(node.right, distance);

        // Count pairs from different subtrees
        for (int l : left) {
            for (int r : right) {
                if (l + r <= distance) {
                    result++;
                }
            }
        }

        // Return updated distances for parent
        List<Integer> current = new ArrayList<>();
        for (int d : left) {
            if (d + 1 <= distance) current.add(d + 1);
        }
        for (int d : right) {
            if (d + 1 <= distance) current.add(d + 1);
        }

        return current;
    }
}

RETURN LIST OF VALUES

Pattern: Return list/array of values instead of single value

Each value represents a different path/node
Parent combines lists from children

Use case: Need to track multiple paths/distances from subtree

14. Path Sum III (LC 437)

State Definition: Count paths ending at each node with target sum

Approach: Prefix sum with HashMap

class Solution {
    int count = 0;
    int target;

    public int pathSum(TreeNode root, int targetSum) {
        this.target = targetSum;
        Map<Long, Integer> prefixSum = new HashMap<>();
        prefixSum.put(0L, 1);  // empty prefix
        dfs(root, 0L, prefixSum);
        return count;
    }

    private void dfs(TreeNode node, long currentSum, Map<Long, Integer> prefixSum) {
        if (node == null) return;

        currentSum += node.val;

        // Check if there's a prefix we can remove to get target
        count += prefixSum.getOrDefault(currentSum - target, 0);

        // Add current prefix
        prefixSum.put(currentSum, prefixSum.getOrDefault(currentSum, 0) + 1);

        dfs(node.left, currentSum, prefixSum);
        dfs(node.right, currentSum, prefixSum);

        // Backtrack
        prefixSum.put(currentSum, prefixSum.get(currentSum) - 1);
    }
}

PREFIX SUM ON TREE

Pattern: Extend prefix sum technique to trees

Track sum along path from root
Use HashMap to find complementary prefix
Backtrack when returning from subtree

Formula: count += prefixSum[currentSum - target]

15. All Nodes Distance K in Binary Tree (LC 863)

Approach: Convert tree to graph, then BFS from target

class Solution {
    Map<TreeNode, TreeNode> parent = new HashMap<>();

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        // Build parent pointers
        buildParent(root, null);

        // BFS from target
        Queue<TreeNode> queue = new LinkedList<>();
        Set<TreeNode> visited = new HashSet<>();
        queue.offer(target);
        visited.add(target);

        int distance = 0;
        while (!queue.isEmpty() && distance < k) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                // Add left child
                if (node.left != null && !visited.contains(node.left)) {
                    queue.offer(node.left);
                    visited.add(node.left);
                }

                // Add right child
                if (node.right != null && !visited.contains(node.right)) {
                    queue.offer(node.right);
                    visited.add(node.right);
                }

                // Add parent
                TreeNode par = parent.get(node);
                if (par != null && !visited.contains(par)) {
                    queue.offer(par);
                    visited.add(par);
                }
            }
            distance++;
        }

        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            result.add(queue.poll().val);
        }
        return result;
    }

    private void buildParent(TreeNode node, TreeNode par) {
        if (node == null) return;
        parent.put(node, par);
        buildParent(node.left, node);
        buildParent(node.right, node);
    }
}

Category 4: Tree Matching/Coloring

16. Minimum Height Trees (LC 310)

PROBLEM

A tree is an undirected graph where any two vertices are connected by exactly one path.

Find all MHTs (Minimum Height Trees) - trees with minimum height when rooted at different nodes.

Approach: Find tree center(s) using topological sort

Remove leaves layer by layer
Center(s) = last 1-2 nodes remaining

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);

        List<Set<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new HashSet<>());
        }

        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        // Find initial leaves
        Queue<Integer> leaves = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (graph.get(i).size() == 1) {
                leaves.offer(i);
            }
        }

        int remaining = n;
        while (remaining > 2) {
            int size = leaves.size();
            remaining -= size;

            for (int i = 0; i < size; i++) {
                int leaf = leaves.poll();

                // Remove leaf from its neighbor
                int neighbor = graph.get(leaf).iterator().next();
                graph.get(neighbor).remove(leaf);

                if (graph.get(neighbor).size() == 1) {
                    leaves.offer(neighbor);
                }
            }
        }

        return new ArrayList<>(leaves);
    }
}

TREE CENTER

Key insight: Tree has at most 2 centers

Finding centers: Peel off leaves layer by layer

Similar to topological sort
Last remaining nodes = centers

These centers minimize tree height!

17. Sum Root to Leaf Numbers (LC 129)

State Definition: Accumulate number along path

Top-down: Pass accumulated value to children

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int currentNumber) {
        if (node == null) return 0;

        currentNumber = currentNumber * 10 + node.val;

        // Leaf: return the number
        if (node.left == null && node.right == null) {
            return currentNumber;
        }

        // Internal: sum from both subtrees
        return dfs(node.left, currentNumber) + dfs(node.right, currentNumber);
    }
}

18. Insufficient Nodes in Root to Leaf Paths (LC 1080)

State Definition: Should prune this subtree?

Condition: No path from here to any leaf meets the limit

class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        return dfs(root, 0, limit) ? null : root;
    }

    // Returns true if subtree should be pruned
    private boolean dfs(TreeNode node, int pathSum, int limit) {
        if (node == null) return true;

        pathSum += node.val;

        // Leaf: check if path sum is sufficient
        if (node.left == null && node.right == null) {
            return pathSum < limit;
        }

        boolean pruneLeft = dfs(node.left, pathSum, limit);
        boolean pruneRight = dfs(node.right, pathSum, limit);

        if (pruneLeft) node.left = null;
        if (pruneRight) node.right = null;

        // Prune this node if both children are pruned
        return pruneLeft && pruneRight;
    }
}

19. Maximum Product of Splitted Binary Tree (LC 1339)

Two passes:

Compute total sum
For each subtree, compute product with remaining tree

class Solution {
    long maxProduct = 0;
    long totalSum = 0;

    public int maxProduct(TreeNode root) {
        totalSum = getSum(root);
        getSum(root);  // second pass to compute products
        return (int)(maxProduct % 1_000_000_007);
    }

    private long getSum(TreeNode node) {
        if (node == null) return 0;

        long leftSum = getSum(node.left);
        long rightSum = getSum(node.right);
        long subtreeSum = node.val + leftSum + rightSum;

        // If totalSum is set (second pass), compute product
        if (totalSum != 0) {
            long product = subtreeSum * (totalSum - subtreeSum);
            maxProduct = Math.max(maxProduct, product);
        }

        return subtreeSum;
    }
}

20. Time Needed to Inform All Employees (LC 1376)

State Definition: dp[node] = max time to inform all subordinates

Transition: inform_time[node] + max(child_times)

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        // Build tree
        List<List<Integer>> subordinates = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            subordinates.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                subordinates.get(manager[i]).add(i);
            }
        }

        return dfs(headID, subordinates, informTime);
    }

    private int dfs(int employee, List<List<Integer>> subordinates, int[] informTime) {
        int maxSubordinateTime = 0;

        for (int sub : subordinates.get(employee)) {
            maxSubordinateTime = Math.max(maxSubordinateTime, dfs(sub, subordinates, informTime));
        }

        return informTime[employee] + maxSubordinateTime;
    }
}

The Common Thread

WHAT MAKES THESE ALL THE SAME PATTERN?

Every tree DP problem has:

State: dp[node] or dp[node][state] = answer for subtree rooted at node
Traversal: DFS (usually post-order) to process children before parent
Combine step: Merge children's solutions to compute parent's solution
Base case: Leaves or null nodes
Goal: Bottom-up propagation of information

Key Insight: Trees are recursive structures. The answer for a node depends on answers for its children. Process children first (post-order), then combine their results.

Classic Code Structure

Single Pass (Post-Order)

class Solution {
    int answer = 0;  // global tracker if needed

    public int solve(TreeNode root) {
        dfs(root);
        return answer;
    }

    private int[] dfs(TreeNode node) {
        // Base case
        if (node == null) return baseCase;

        // Process children first (post-order)
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        // Combine children's solutions
        int[] current = combine(left, right, node);

        // Update global answer if needed
        answer = update(answer, current);

        // Return info to parent
        return current;
    }
}

Two Passes (Re-rooting)

class Solution {
    int[] answer;
    int[] subtreeInfo;

    public int[] solve(TreeNode root) {
        // Pass 1: compute for subtrees (bottom-up)
        dfs1(root);

        // Pass 2: adjust using parent info (top-down)
        dfs2(root, null);

        return answer;
    }

    // Pass 1: Bottom-up
    private void dfs1(TreeNode node) {
        if (node == null) return;
        dfs1(node.left);
        dfs1(node.right);
        // Compute using children
        subtreeInfo[node] = combine(children);
    }

    // Pass 2: Top-down
    private void dfs2(TreeNode node, TreeNode parent) {
        if (node == null) return;
        // Adjust using parent
        answer[node] = adjust(subtreeInfo[node], parent);
        dfs2(node.left, node);
        dfs2(node.right, node);
    }
}

State Patterns

STATE CAN BE

Single value: dp[node] = one metric

return depth;
return sum;

Tuple: dp[node] = (value1, value2, ...)

return new int[]{notRobbed, robbed};
return new int[]{isBST, size, min, max};

With states: dp[node][state] = value when node is in state

return new int[][]{
    {state0_left, state0_right},
    {state1_left, state1_right}
};

List/Array: Multiple values per node

return List.of(distance1, distance2, ...);

Pattern Recognition Keywords

KEY PATTERNS TO RECOGNIZE

"Maximum/minimum in a tree" → Likely tree DP

"For each subtree..." → Process children first

"Path between nodes" → Combine left + right subtrees

"Decision at each node affects children" → State machine + tree

"Count something in subtrees" → Aggregate children's counts

"Distance/sum from all nodes" → Possibly re-rooting

"Optimal subtree property" → Post-order DP

Pattern Recognition Checklist

USE THIS CHECKLIST

When you see a new problem, ask:

Is the data structure a tree (binary tree, N-ary tree, graph that's a tree)?
Does the answer for a node depend on answers from children?
Can I define dp[node] as "best answer for subtree rooted at node"?
Do I need to combine information from left and right children?
Should I process children before parent (post-order)?

If all YES → Pattern 6: DP on Trees

Common Mistakes

COMMON PITFALLS

Mistake 1: Processing parent before children

// WRONG - trying to use children before computing them
private int dfs(TreeNode node) {
    int result = computeUsingChildren(node);  // children not processed!
    dfs(node.left);
    dfs(node.right);
    return result;
}

// RIGHT - post-order
private int dfs(TreeNode node) {
    int left = dfs(node.left);   // process children first
    int right = dfs(node.right);
    return combine(left, right, node);
}

Mistake 2: Not handling null nodes

// WRONG - will crash on null
private int dfs(TreeNode node) {
    int left = dfs(node.left);  // NPE if node is null!
    ...
}

// RIGHT - check null first
private int dfs(TreeNode node) {
    if (node == null) return baseCase;
    int left = dfs(node.left);
    ...
}

Mistake 3: Confusing "through node" vs "from node"

// For max path sum:
// WRONG - returning path through node
return node.val + left + right;  // uses BOTH branches

// RIGHT - return path FROM node (one branch)
return node.val + Math.max(left, right);  // ONE branch for parent

// Track "through node" separately in global variable

Mistake 4: Forgetting to update global answer

// For diameter, max path, etc.
// WRONG - only returning, not tracking max
return leftDepth + rightDepth;

// RIGHT - track max globally
maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
return 1 + Math.max(leftDepth, rightDepth);

Space Optimization

TREE DP SPACE

Recursion stack: O(h) where h = tree height

Balanced tree: O(log n)
Skewed tree: O(n)

Can't avoid recursion for tree traversal

Optimization strategies:

Use iterative DFS with explicit stack (same space)
Morris traversal (O(1) space, but complex)
For some problems, can compute without storing state

Generally: Accept O(h) space for tree DP

Learning Path

RECOMMENDED ORDER

Week 1: Core Problems (1-5)

House Robber III (state machine on tree)
Max Path Sum, Diameter (combine subtrees)
Tree Cameras (greedy + states)

Week 2: Subtree Properties (6-10)

Univalue Subtrees, Largest BST (validation)
Distribute Coins (balance/flow)
Sum of Distances (re-rooting!)

Week 3: Paths (11-15)

Max Ancestor Diff (top-down)
ZigZag Path (direction states)
Path Sum III (prefix sum on tree)

Week 4: Advanced (16-20)

Minimum Height Trees (tree center)
Max Product Split (two passes)
Time to Inform (simple aggregation)

Total: 20 problems × 4 weeks = Pattern 6 mastery

Quick Reference Table

Problem	State	Traversal	Combine	Pattern Type
House Robber III	[not_rob, rob]	Post-order	max based on states	State machine
Max Path Sum	max_gain	Post-order	node + left + right	Global tracking
Diameter	depth	Post-order	left_depth + right_depth	Metric combination
Tree Cameras	[covered, has_cam, not_covered]	Post-order	Greedy placement	Greedy + DP
Largest BST	[isBST, size, min, max]	Post-order	Validate with bounds	Tuple return
Distribute Coins	balance	Post-order	sum balances	Flow calculation
Sum of Distances	Two passes	Post + Pre	Re-rooting adjustment	Re-rooting
ZigZag Path	[left_len, right_len]	Post-order	Alternate directions	Direction state

Traversal Order Summary

WHEN TO USE WHICH TRAVERSAL

Post-order (most common):

When parent needs children's results
Bottom-up computation
Examples: House Robber III, Diameter, Max Path Sum

Pre-order (top-down):

When children need parent's information
Passing state down
Examples: Max Ancestor Diff, Sum Root to Leaf

Two-pass (re-rooting):

When need answer for all nodes as roots
First pass: compute for one root
Second pass: adjust for others
Example: Sum of Distances in Tree

Next Steps

YOU'VE MASTERED ALL 6 CORE PATTERNS!

Congratulations! You now have comprehensive knowledge of:

✅ Linear Sequence (1D progression)
✅ Grid Traversal (2D progression)
✅ Bounded Knapsack (resource allocation)
✅ Interval DP (range merging)
✅ State Machine (mode transitions)
✅ Tree DP (hierarchical recursion)

Advanced topics (optional):

Bitmask DP (subset states)
Digit DP (number constraints)
DP with data structures (segment trees, etc.)

You're ready to tackle 95% of DP problems on LeetCode!

Final Thoughts

TREE DP IS THE RECURSIVE PATTERN

Tree DP teaches you to think recursively on hierarchies.

Master these 20 problems, and you'll:

Recognize tree recursion instantly
Know when to use post-order vs pre-order
Handle state machines on trees
Combine information from subtrees naturally
Use re-rooting for advanced problems

This is your hierarchical foundation. You've completed the journey!

Summary: The Tree DP Template

// Template for Tree DP
class Solution {
    int globalAnswer = 0;  // if needed

    public int solve(TreeNode root) {
        dfs(root);
        return globalAnswer;
    }

    // Returns state info for this subtree
    private int[] dfs(TreeNode node) {
        // Base case: null node
        if (node == null) {
            return baseCase;  // e.g., new int[]{0, 0}
        }

        // Post-order: process children first
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        // Combine children's solutions
        int[] current = new int[numStates];
        for (int state = 0; state < numStates; state++) {
            current[state] = combine(left, right, node, state);
        }

        // Update global answer (if tracking separately)
        globalAnswer = Math.max(globalAnswer, computeGlobal(current));

        // Return state for parent to use
        return current;
    }
}

REMEMBER THE MANTRA

"Trees are recursive. Process children first (post-order), combine their solutions, return result to parent. The base case is null or leaf nodes."

This is the essence of Tree DP.

Congratulations!

🎉 YOU'VE COMPLETED THE DP MASTERY CURRICULUM

100+ problems across 6 core patterns

You now have the mental models and templates to solve any DP problem!

Keep practicing, and these patterns will become second nature. 🚀

The Core Pattern​

Pattern Recognition​

Category 1: Core Tree DP Problems​

1. House Robber III (LC 337)​

2. Binary Tree Maximum Path Sum (LC 124)​

3. Diameter of Binary Tree (LC 543)​

4. Longest Univalue Path (LC 687)​

5. Binary Tree Cameras (LC 968)​

Category 2: Subtree Properties​

6. Count Univalue Subtrees (LC 250)​

7. Largest BST Subtree (LC 333)​

8. Most Frequent Subtree Sum (LC 508)​

9. Distribute Coins in Binary Tree (LC 979)​

10. Sum of Distances in Tree (LC 834)​

Category 3: Path/Distance Problems​

11. Maximum Difference Between Node and Ancestor (LC 1026)​

12. Longest ZigZag Path in Binary Tree (LC 1372)​

13. Number of Good Leaf Nodes Pairs (LC 1530)​

14. Path Sum III (LC 437)​

15. All Nodes Distance K in Binary Tree (LC 863)​

Category 4: Tree Matching/Coloring​

16. Minimum Height Trees (LC 310)​

17. Sum Root to Leaf Numbers (LC 129)​

18. Insufficient Nodes in Root to Leaf Paths (LC 1080)​

19. Maximum Product of Splitted Binary Tree (LC 1339)​

20. Time Needed to Inform All Employees (LC 1376)​

The Common Thread​

Classic Code Structure​

Single Pass (Post-Order)​

Two Passes (Re-rooting)​

State Patterns​

Pattern Recognition Keywords​

Pattern Recognition Checklist​

Common Mistakes​

Mistake 1: Processing parent before children​

Mistake 2: Not handling null nodes​

Mistake 3: Confusing "through node" vs "from node"​

Mistake 4: Forgetting to update global answer​

Space Optimization​

Learning Path​

Quick Reference Table​

Traversal Order Summary​

Next Steps​

Final Thoughts​

Summary: The Tree DP Template​

Congratulations!​

The Core Pattern

Pattern Recognition

Category 1: Core Tree DP Problems

1. House Robber III (LC 337)

2. Binary Tree Maximum Path Sum (LC 124)

3. Diameter of Binary Tree (LC 543)

4. Longest Univalue Path (LC 687)

5. Binary Tree Cameras (LC 968)

Category 2: Subtree Properties

6. Count Univalue Subtrees (LC 250)

7. Largest BST Subtree (LC 333)

8. Most Frequent Subtree Sum (LC 508)

9. Distribute Coins in Binary Tree (LC 979)

10. Sum of Distances in Tree (LC 834)

Category 3: Path/Distance Problems

11. Maximum Difference Between Node and Ancestor (LC 1026)

12. Longest ZigZag Path in Binary Tree (LC 1372)

13. Number of Good Leaf Nodes Pairs (LC 1530)

14. Path Sum III (LC 437)

15. All Nodes Distance K in Binary Tree (LC 863)

Category 4: Tree Matching/Coloring

16. Minimum Height Trees (LC 310)

17. Sum Root to Leaf Numbers (LC 129)

18. Insufficient Nodes in Root to Leaf Paths (LC 1080)

19. Maximum Product of Splitted Binary Tree (LC 1339)

20. Time Needed to Inform All Employees (LC 1376)

The Common Thread

Classic Code Structure

Single Pass (Post-Order)

Two Passes (Re-rooting)

State Patterns

Pattern Recognition Keywords

Pattern Recognition Checklist

Common Mistakes

Mistake 1: Processing parent before children

Mistake 2: Not handling null nodes

Mistake 3: Confusing "through node" vs "from node"

Mistake 4: Forgetting to update global answer

Space Optimization

Learning Path

Quick Reference Table

Traversal Order Summary

Next Steps

Final Thoughts

Summary: The Tree DP Template

Congratulations!