DP on Trees Maximum Path Sum in DSA Java

Mental Model

We find the biggest sum of values along any path in a tree by checking each node's best paths through its children.

Analogy: Imagine climbing a mountain with many paths. You want to find the highest total elevation gain by choosing the best route that can go up and down but never revisits the same spot.

      1
     / \
    2   3
   / 
  4  
Each node has a value. We want the path with the largest sum of these values.

Dry Run Walkthrough

Input: Tree: 1(10) -> 2(2), 3(10); 2 -> 4(20); Find max path sum

Goal: Find the maximum sum of values on any path in the tree

Step 1: Start DFS at node 4 (leaf)

Node 4: max single path = 20, max path sum = 20

Why: Leaf nodes have max path sum equal to their own value

Step 2: Return to node 2, calculate max single path including child 4

Node 2: max single path = max(2, 2+20) = 22, max path sum = max(20, 22) = 22

Why: Node 2 can extend path from child 4 or start fresh

Step 3: Visit node 3 (leaf)

Node 3: max single path = 10, max path sum = 10

Why: Leaf node max path sum is its own value

Step 4: Return to node 1, calculate max single path and max path sum using children 2 and 3

Node 1: max single path = max(10, 10+22, 10+10) = 32
Max path sum candidates: 22 (from 2), 10 (from 3), 10+22+10=42 (path through 2,1,3)
Max path sum = 42

Why: Node 1 can connect paths from both children through itself for max sum

Result:

Max path sum = 42

Annotated Code

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class MaxPathSum {
    private int maxSum = Integer.MIN_VALUE;

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

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

        // max path sum on left child, ignore negatives
        int left = Math.max(0, dfs(node.left));
        // max path sum on right child, ignore negatives
        int right = Math.max(0, dfs(node.right));

        // max path sum passing through this node
        int currentMax = node.val + left + right;

        // update global max if current path is better
        maxSum = Math.max(maxSum, currentMax);

        // return max path sum extending to parent
        return node.val + Math.max(left, right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(2);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(20);

        MaxPathSum solver = new MaxPathSum();
        System.out.println(solver.maxPathSum(root));
    }
}

if (node == null) return 0;

stop recursion at leaf's child

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

get max path sum from left child ignoring negative sums

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

get max path sum from right child ignoring negative sums

int currentMax = node.val + left + right;

calculate max path sum passing through current node

maxSum = Math.max(maxSum, currentMax);

update global max path sum if current is better

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

return max path sum extending to parent node

Output

42

Complexity Analysis

Time: O(n) because each node is visited once in DFS

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach checking all paths is O(n^2) or worse; DP on trees is efficient by reusing results

Edge Cases

Tree with all negative values

Algorithm returns the largest single node value as max path sum

DSA Java

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

Single node tree

Returns the node's value as max path sum

DSA Java

if (node == null) return 0;

Tree with one child nodes only

Correctly computes max path sum along the single path

DSA Java

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

When to Use This Pattern

When asked for the maximum sum path in a tree that can start and end anywhere, use DP on trees with DFS to combine child results efficiently.

Common Mistakes

Mistake: Not ignoring negative child path sums, which lowers the max sum
Fix: Use Math.max(0, childSum) to ignore negative sums

Mistake: Returning sum of both children to parent, which breaks path definition
Fix: Return node value plus max of one child's sum only

Summary

Finds the maximum sum of values along any path in a binary tree.

Use when you need the highest sum path that can start and end at any node.

The key is to combine max sums from children ignoring negatives and update global max including both children.

Practice

1. What does the "maximum path sum" in a binary tree represent?
Maximum path sum means the largest sum of node values along any path in the tree.

easy

A. The sum of node values from root to the deepest leaf

B. The sum of all node values in the tree

C. The maximum value of a single node in the tree

D. The largest sum of node values along any path in the tree

Solution

1. Step 1: Understand the definition of maximum path sum

   The maximum path sum is the highest sum you can get by adding node values along any path in the tree. The path can start and end at any nodes.

2. Step 2: Differentiate from other sums

   It is not just the sum of all nodes, nor the max single node, nor limited to root-to-leaf paths. It considers any path.

3. Final Answer:

   The largest sum of node values along any path in the tree -> Option D

4. Quick Check:

   Maximum path sum = largest path sum [OK]

Hint: Maximum path sum is any path's largest sum, not just root paths [OK]

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking path must start at root
• Considering only single node values

2. Which of the following Java method signatures is correct for a recursive function to find maximum path sum in a binary tree node class named TreeNode?

easy

A. int maxPathSum(TreeNode root) throws Exception

B. public int maxPathSum(TreeNode root)

C. void maxPathSum(TreeNode root)

D. public static maxPathSum(TreeNode root)

Solution

1. Step 1: Check method return type and parameters

   The method should return an int (the max sum) and accept a TreeNode parameter.

2. Step 2: Validate Java syntax

   public int maxPathSum(TreeNode root) uses correct syntax. int maxPathSum(TreeNode root) throws Exception unnecessarily throws Exception, the void version returns wrong type, the version without return type is invalid.

3. Final Answer:

   public int maxPathSum(TreeNode root) -> Option B

4. Quick Check:

   Correct method signature returns int and takes TreeNode [OK]

Hint: Method must return int and accept TreeNode parameter [OK]

Common Mistakes:

• Using void return type instead of int
• Missing return type in method signature
• Adding unnecessary throws Exception

3. Given the following Java code snippet for maximum path sum in a binary tree, what is the printed output?

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int v) { val = v; }
}

public 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;
    int leftGain = Math.max(maxGain(node.left), 0);
    int rightGain = Math.max(maxGain(node.right), 0);
    int priceNewPath = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, priceNewPath);
    return node.val + Math.max(leftGain, rightGain);
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(-10);
    root.left = new TreeNode(9);
    root.right = new TreeNode(20);
    root.right.left = new TreeNode(15);
    root.right.right = new TreeNode(7);
    Solution sol = new Solution();
    System.out.println(sol.maxPathSum(root));
  }
}

medium

A. 42

B. 35

C. 27

D. 20

Solution

1. Step 1: Trace maxGain for each node

   Calculate maxGain for leaves: 9 returns 9, 15 returns 15, 7 returns 7. For node 20: leftGain=15, rightGain=7, priceNewPath=20+15+7=42, maxSum=42. For root -10: leftGain=9, rightGain=20+15=35 (maxGain returns node.val + max(leftGain,rightGain), so for right child maxGain=35), priceNewPath at root = -10 + 9 + 35 = 34, maxSum remains 42.

2. Step 2: Determine maxSum after full traversal

   maxSum is updated to 42 at node 20, which is the maximum path sum.

3. Final Answer:

   42 -> Option A

4. Quick Check:

   Max path sum = 42 [OK]

Hint: Max path sum includes node plus max gains from left and right [OK]

Common Mistakes:

• Ignoring negative node values
• Not resetting maxSum correctly
• Confusing return value with maxSum

4. Identify the bug in this Java method for maximum path sum and select the fix:

private int maxGain(TreeNode node) {
  if (node == null) return 0;
  int leftGain = maxGain(node.left);
  int rightGain = maxGain(node.right);
  int priceNewPath = node.val + leftGain + rightGain;
  maxSum = Math.max(maxSum, priceNewPath);
  return node.val + Math.max(leftGain, rightGain);
}

medium

A. Change return type to void

B. Remove maxSum update line

C. Add Math.max(..., 0) to leftGain and rightGain to ignore negative sums

D. Return node.val + leftGain + rightGain instead

Solution

1. Step 1: Analyze handling of negative gains

   Without Math.max(..., 0), negative leftGain or rightGain reduce path sum incorrectly.

2. Step 2: Fix by ignoring negative gains

   Use int leftGain = Math.max(maxGain(node.left), 0) and similarly for rightGain to ignore negative paths.

3. Final Answer:

   Add Math.max(..., 0) to leftGain and rightGain to ignore negative sums -> Option C

4. Quick Check:

   Ignore negative gains with Math.max(..., 0) [OK]

Hint: Ignore negative child sums by max with zero [OK]

Common Mistakes:

• Not ignoring negative sums causing wrong maxSum
• Changing return type incorrectly
• Removing maxSum update line

5. You want to find the maximum path sum in a binary tree where nodes can have negative values. Which approach correctly applies dynamic programming on trees to solve this?

Choose the best description of the approach.

hard

A. Use post-order traversal; at each node, compute max gain from left and right ignoring negatives; update global max with node value plus both gains; return node value plus max gain of one side

B. Use pre-order traversal; sum all node values; return the sum as max path sum

C. Use in-order traversal; keep track of max node value only; return max node value

D. Use level-order traversal; sum values at each level; return max level sum

Solution

1. Step 1: Understand dynamic programming on trees

   Post-order traversal ensures children are processed before parent, allowing calculation of max gains from subtrees.

2. Step 2: Apply max gain logic ignoring negative sums

   At each node, calculate max gain from left and right children ignoring negatives, update global max path sum with node plus both gains, and return node plus max gain of one side for parent's use.

3. Final Answer:

   Use post-order traversal; at each node, compute max gain from left and right ignoring negatives; update global max with node value plus both gains; return node value plus max gain of one side -> Option A

4. Quick Check:

   Post-order + max gain ignoring negatives = correct DP approach [OK]

Hint: Use post-order and ignore negative gains for max path sum [OK]

Common Mistakes:

• Using wrong traversal order
• Summing all nodes instead of max path
• Ignoring negative values in gains