DP on Trees Maximum Path Sum in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Path Sum in a Simple Binary Tree

What is the output of the following Java code that calculates the maximum path sum in a binary tree?

DSA Java

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

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 class Main {
    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));
    }
}

A 35

B 20

C 27

D 42

💡 Hint

Consider the path that includes both left and right children of node 20.

The maximum path sum is 42, coming from the path 15 -> 20 -> 7, plus the node 20 itself, and ignoring the negative root -10 for the maximum sum path.

🧠 Conceptual

intermediate

Understanding the Role of maxGain Function

In the DP solution for maximum path sum in a binary tree, what does the helper function maxGain(node) represent?

A The maximum sum of any path in the entire tree rooted at node.

B The maximum sum of a path starting from the node and going down to any leaf.

C The sum of all node values in the subtree rooted at node.

D The maximum sum of a path that must include the node and both its children.

💡 Hint

Think about what the function returns to its parent call.

maxGain(node) returns the maximum sum of a path starting at node and extending downwards to one child or none, which helps build the maximum path sum including or excluding the node.

🔧 Debug

advanced

Identify the Error in Maximum Path Sum Calculation

What error does the following code produce when calculating maximum path sum in a binary tree?

DSA Java

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 = 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);
    }
}

A SyntaxError due to missing return statement

B StackOverflowError due to infinite recursion

C Incorrect maximum path sum when negative values are present

D NullPointerException when node is null

💡 Hint

Consider how negative gains affect the path sum calculation.

The code does not ignore negative gains by using Math.max with 0, so negative child paths reduce the sum incorrectly.

❓ Predict Output

advanced

Output of Maximum Path Sum with Negative Nodes

What is the output of the following Java code that calculates the maximum path sum in a binary tree with negative values?

DSA Java

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

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 class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(-3);
        Solution sol = new Solution();
        System.out.println(sol.maxPathSum(root));
    }
}

A -3

B 0

C 3

D Integer.MIN_VALUE

💡 Hint

The tree has only one node with a negative value.

The maximum path sum is the single node value -3 because no positive gain paths exist.

🚀 Application

expert

Maximum Path Sum in a Tree with Multiple Branches

Given a binary tree with nodes having values [1, 2, 3, 4, 5, 6, 7] arranged as a complete binary tree, what is the maximum path sum?

DSA Java

/* Tree structure:
        1
       / \
      2   3
     / \ / \
    4  5 6  7
*/

A 18

B 16

C 22

D 28

💡 Hint

Consider the path that goes through the root and both children with their maximum gains.

The maximum path sum is 18, coming from path 5 -> 2 -> 1 -> 3 -> 7.

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