DP on Trees Maximum Path Sum in DSA Java - Build from Scratch

DP on Trees Maximum Path Sum

📖 Scenario: You are working with a tree data structure representing a network of connected nodes. Each node has a value that can be positive or negative. You want to find the maximum sum of values along any path in the tree. A path can start and end at any nodes but must follow the tree edges.

🎯 Goal: Build a Java program that uses dynamic programming on trees to find the maximum path sum. You will create the tree nodes, set up a helper variable, write the core recursive logic to compute the maximum path sum, and finally print the result.

📋 What You'll Learn

Create a TreeNode class with int val, TreeNode left, and TreeNode right fields

Build a specific tree with given node values and structure

Use a helper variable maxSum to track the maximum path sum found

Write a recursive method maxPathSumHelper(TreeNode node) that returns the max path sum from the current node downwards

Update maxSum inside the recursive method to track the global maximum path sum

Print the final maxSum after processing the tree

💡 Why This Matters

🌍 Real World

Finding maximum path sums in trees is useful in network analysis, decision trees, and optimizing routes where nodes represent costs or values.

💼 Career

Understanding dynamic programming on trees is important for software engineers working on algorithms, game development, and systems involving hierarchical data.

1

Create the TreeNode class and build the tree

Create a TreeNode class with int val, TreeNode left, and TreeNode right fields. Then create the root node with value 1, its left child with value 2, and its right child with value 3. Also create the left child of node 2 with value 4 and the right child of node 2 with value 5.

DSA Java

// Define TreeNode class and build the tree
// Your code here

Hint

Start by defining the TreeNode class with the required fields and constructor. Then create the nodes and link them as described.

2

Add a helper variable to track maximum path sum

Inside the Main class, add a static integer variable called maxSum and initialize it to Integer.MIN_VALUE.

DSA Java

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

public class Main {
    static int maxSum = Integer.MIN_VALUE; // Your code here

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
    }
}

Hint

Add a static variable maxSum in the Main class to keep track of the maximum path sum found so far.

3

Write the recursive method to compute maximum path sum

Inside the Main class, write a static method called maxPathSumHelper(TreeNode node) that returns an int. It should return 0 if node is null. Otherwise, recursively call itself on node.left and node.right to get left and right sums, but use Math.max(0, ...) to ignore negative sums. Then update maxSum with the maximum of its current value and node.val + left + right. Finally, return node.val + Math.max(left, right).

DSA Java

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

public class Main {
    static int maxSum = Integer.MIN_VALUE;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
    }

    // Write maxPathSumHelper method below
    // Your code here
}

Hint

Use recursion to get the maximum path sums from left and right children. Ignore negative sums by using Math.max(0, ...). Update the global maxSum with the sum including both children and the current node. Return the maximum sum path that can be extended to the parent.

4

Call the helper and print the maximum path sum

In the main method, call maxPathSumHelper(root) to compute the maximum path sums. Then print the value of maxSum using System.out.println(maxSum);.

DSA Java

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

public class Main {
    static int maxSum = Integer.MIN_VALUE;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // Call maxPathSumHelper and print maxSum
        // Your code here
    }

    static int maxPathSumHelper(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = Math.max(0, maxPathSumHelper(node.left));
        int right = Math.max(0, maxPathSumHelper(node.right));
        maxSum = Math.max(maxSum, node.val + left + right);
        return node.val + Math.max(left, right);
    }
}

Hint

Call the recursive helper on the root node to update maxSum. Then print maxSum to see the maximum path sum.

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