🌲 Blog 8: Dynamic Programming on Trees (Tree DP)

[Dev Cookies]

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​

1. Minimum Vertex Cover on Tree (classic DP): choose minimum nodes such that every edge is covered.
2. Tree Coloring DP: assign colors with constraints (used in graph + tree DP).
3. 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.

Continue reading...

 

Join 𝕋𝕄𝕋 on Telegram
Channel PREVIEW: