Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Tree DP
DSA

Tree DP

Learn how to combine tree traversal with dynamic programming to solve optimization and counting problems.

Tree DP combines post-order DFS with state tracking at each node — each node computes a result based on its children’s results.

Its core advantage:

Post-order traversal naturally computes children first, making subtree DP O(n) with a single pass.

Focus on recognizing:

“Subtree” + “Combine child results” + “Optimization on tree” = Tree DP

Pattern Table

PatternTypical QuestionsTrigger
Max Path SumMaximum path between any nodesLeft + right + current
House RobberMax sum, no adjacent nodesInclude/exclude states
Subtree CombineGeneral child-result DPReturn multiple values per node

Mental Trigger

Children return DP states → Parent combines → Choose best → Bubble up.

1. Generic Java Tree DP Template (Base)

public int treeDP(TreeNode root) {
    if (root == null) return 0;

    int left = treeDP(root.left);
    int right = treeDP(root.right);

    // combine left, right, and root values
    return Math.max(left, right) + root.val;
}
def tree_dp(root):
    if root is None:
        return 0

    left = tree_dp(root.left)
    right = tree_dp(root.right)

    # combine left, right, and root values
    return max(left, right) + root.val
int treeDP(TreeNode* root) {
    if (root == nullptr) return 0;

    int left = treeDP(root->left);
    int right = treeDP(root->right);

    // combine left, right, and root values
    return max(left, right) + root->val;
}
function treeDP(root) {
  if (root === null) return 0;

  const left = treeDP(root.left);
  const right = treeDP(root.right);

  // combine left, right, and root values
  return Math.max(left, right) + root.val;
}

Everything else in Tree DP is just a modification of this template.

Pattern 1: Maximum Path Sum

Bend candidates at every node while gains bubble upward; negatives get pruned. Press ▶ to animate.

Binary Tree Maximum Path Sum

Find the maximum sum of any node-to-node path, where the path may bend at one node.

For each node compute gain = val + max(0, gain(L), gain(R)) — the best it can offer upward. A bend through the node equals val + gainL + gainR; track the global max. The max(0,…) prunes negative subtrees.

TREE VISUALIZER
Steps –
-10920157
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        gain(node) = val + max(0, gain(L), gain(R))
                      
                        2
                        at each node: bend = val + gainL + gainR
                      
                        3
                        answer = max(bend)

Java Code

public int maxPathSum(TreeNode root) {
    int[] max = {Integer.MIN_VALUE};
    dfs(root, max);
    return max[0];
}

private int dfs(TreeNode root, int[] max) {
    if (root == null) return 0;

    int left = Math.max(0, dfs(root.left, max));
    int right = Math.max(0, dfs(root.right, max));

    max[0] = Math.max(max[0], left + right + root.val);

    return Math.max(left, right) + root.val;
}
def max_path_sum(root):
    max_sum = [float('-inf')]
    dfs(root, max_sum)
    return max_sum[0]

def dfs(root, max_sum):
    if root is None:
        return 0

    left = max(0, dfs(root.left, max_sum))
    right = max(0, dfs(root.right, max_sum))

    max_sum[0] = max(max_sum[0], left + right + root.val)

    return max(left, right) + root.val
int maxPathSum(TreeNode* root) {
    int maxSum = INT_MIN;
    dfs(root, maxSum);
    return maxSum;
}

int dfs(TreeNode* root, int& maxSum) {
    if (root == nullptr) return 0;

    int left = max(0, dfs(root->left, maxSum));
    int right = max(0, dfs(root->right, maxSum));

    maxSum = max(maxSum, left + right + root->val);

    return max(left, right) + root->val;
}
function maxPathSum(root) {
  const max = [-Infinity];
  dfs(root, max);
  return max[0];
}

function dfs(root, max) {
  if (root === null) return 0;

  const left = Math.max(0, dfs(root.left, max));
  const right = Math.max(0, dfs(root.right, max));

  max[0] = Math.max(max[0], left + right + root.val);

  return Math.max(left, right) + root.val;
}

What Changed from the Base Template?

Clamp negative contributions

Added:

int left = Math.max(0, dfs(root.left, max));
int right = Math.max(0, dfs(root.right, max));

because negative path sums can be ignored — a path doesn’t have to include negative branches.

Track max across all splits

Added:

max[0] = Math.max(max[0], left + right + root.val);

because the max path might pass through the current node, connecting left and right subtrees.

Max Path Sum = DFS + Clamp negatives to 0 + Track max(left + right + root).

Pattern 2: House Robber III

(rob, skip) pairs per node — tree DP with two states. Press ▶ to animate.

House Robber III

Maximize the sum of robbed nodes in a tree, where robbing a node forbids robbing its children.

Return a (rob, skip) pair per node: rob = val + sum of children's skips, skip = sum of children's max(rob, skip). Combine bottom-up; the answer is max of the root's pair.

TREE VISUALIZER
Steps –
323'3''
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        rob(n)   = n.val + skip(L) + skip(R)
                      
                        2
                        skip(n)  = max(rob/skip of kids)
                      
                        3
                        answer = max(rob(root), skip(root))

Java Code

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

// returns [include, exclude]
private int[] dfs(TreeNode root) {
    if (root == null)
        return new int[]{0, 0};

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

    int include = root.val + left[1] + right[1];
    int exclude = Math.max(left[0], left[1])
                + Math.max(right[0], right[1]);

    return new int[]{include, exclude};
}
def rob(root):
    result = dfs(root)
    return max(result[0], result[1])

# returns [include, exclude]
def dfs(root):
    if root is None:
        return [0, 0]

    left = dfs(root.left)
    right = dfs(root.right)

    include = root.val + left[1] + right[1]
    exclude = max(left[0], left[1]) + max(right[0], right[1])

    return [include, exclude]
int rob(TreeNode* root) {
    vector<int> result = dfs(root);
    return max(result[0], result[1]);
}

// returns {include, exclude}
vector<int> dfs(TreeNode* root) {
    if (root == nullptr)
        return {0, 0};

    vector<int> left = dfs(root->left);
    vector<int> right = dfs(root->right);

    int include = root->val + left[1] + right[1];
    int exclude = max(left[0], left[1])
                + max(right[0], right[1]);

    return {include, exclude};
}
function rob(root) {
  const result = dfs(root);
  return Math.max(result[0], result[1]);
}

// returns [include, exclude]
function dfs(root) {
  if (root === null)
    return [0, 0];

  const left = dfs(root.left);
  const right = dfs(root.right);

  const include = root.val + left[1] + right[1];
  const exclude = Math.max(left[0], left[1])
                + Math.max(right[0], right[1]);

  return [include, exclude];
}

What Changed from the Base Template?

Two-state return

Base:

return Math.max(left, right) + root.val; // single value

Changed:

return new int[]{include, exclude}; // two states

because each node needs to return both possibilities: rob this node or skip it.

State transition

Added:

int include = root.val + left[1] + right[1];
int exclude = Math.max(left[0], left[1])
            + Math.max(right[0], right[1]);

include = current value + children excluded. exclude = best of each child (include or exclude).

House Robber = Two-state DP: [include, exclude] + Transition based on child states.

Tree DP Pattern Evolution

Base Tree DP (post-order + combine)
    ↓
Max Path Sum
    (+ clamp negatives + track split max)
    ↓
House Robber
    (+ two states: [include, exclude] + transition)

Common Mistakes

Not handling negative values.

Max path sum should clamp negative child contributions to 0.

Single-state return when two-state is needed.

If a node’s decision depends on whether children were taken, return multiple states.

Using pre-order instead of post-order.

Tree DP requires children results first — must be post-order.

Recognition Cheat Sheet

If you see…Think…
Max path sum in treeDFS + clamp negatives
Tree with choose/skip constraintTwo-state DP
Subtree optimizationPost-order DP
Combine child resultsTree DP

My Private Notes

Notes are auto-saved locally to this device.