Maximum Path Sum in Binary Tree in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Path Sum Calculation

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 val) { this.val = val; }
}

public class Solution {
    private 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));
    }
}

A 20

B 35

C 27

D 42

💡 Hint

Consider the path that includes the root's right subtree and both its children.

The maximum path sum is 42, coming from the path 15 -> 20 -> 7. The root's value -10 is not included in the max path sum because it reduces the total. The path 9 alone is smaller. The code calculates max gains from left and right subtrees and updates the maxSum accordingly.

🧠 Conceptual

intermediate

Understanding the Role of maxGain Function

In the maximum path sum algorithm for a binary tree, what is the main purpose of the maxGain function?

A To find the maximum sum of any path in the entire tree regardless of node connections.

B To count the number of nodes in the longest path of the tree.

C To calculate the maximum sum of a path that starts at the current node and extends downwards to one child only.

D To find the minimum value node in the binary tree.

💡 Hint

Think about how the function returns values to its parent calls.

maxGain returns the maximum sum of a path starting from the current node and extending down to one child, which helps in calculating the maximum path sum that can be formed including the current node.

🔧 Debug

advanced

Identify the Error in Maximum Path Sum Code

What error will occur when running the following code snippet for maximum path sum in a binary tree?

DSA Java

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

public class Solution {
    private int maxSum = 0;

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

A NullPointerException at runtime.

B The code returns incorrect results for trees with negative values.

C StackOverflowError due to infinite recursion.

D Compilation error due to missing return statement.

💡 Hint

Consider the initial value of maxSum and how negative values affect it.

maxSum is initialized to 0, so if all node values are negative, maxSum will never update correctly, resulting in incorrect output. It should be initialized to Integer.MIN_VALUE to handle negative values properly.

❓ Predict Output

advanced

Output of Maximum Path Sum for Single Node Tree

What is the output of the following Java code when the binary tree has only one node with value -5?

DSA Java

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

public class Solution {
    private 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(-5);
        Solution sol = new Solution();
        System.out.println(sol.maxPathSum(root));
    }
}

A -5

B 5

C Integer.MIN_VALUE

D 0

💡 Hint

The maximum path sum can be a single node value if all others are null.

Since the tree has only one node with value -5, the maximum path sum is -5 itself. The code correctly handles negative values by initializing maxSum to Integer.MIN_VALUE.

🧠 Conceptual

expert

Why Use Math.max with 0 in maxGain Function?

In the maximum path sum algorithm, why do we use Math.max(maxGain(node.left), 0) when calculating leftGain?

A To ignore negative path sums from the left subtree, as they would reduce the total path sum.

B To ensure the left subtree is always included in the path sum calculation.

C To prioritize the left subtree over the right subtree in the path sum.

D To handle null nodes by converting them to zero values.

💡 Hint

Think about how negative values affect the total path sum.

Using Math.max with 0 ignores negative sums from subtrees, preventing them from decreasing the overall path sum. This ensures only positive contributions are added.

Practice

1. What does the Maximum Path Sum in Binary Tree problem ask you to find?

easy

A. The highest sum of values along any path in the tree

B. The longest path length in the tree

C. The smallest value in the tree

D. The number of leaf nodes in the tree

Solution

1. Step 1: Understand the problem goal

   The problem asks for the maximum sum of node values along any path in the binary tree. A path can start and end at any node but must be connected.

2. Step 2: Differentiate from other tree metrics

   It is not about path length, smallest value, or leaf count. It focuses on sum of node values along a path.

3. Final Answer:

   The highest sum of values along any path in the tree -> Option A

4. Quick Check:

   Maximum path sum = highest sum of connected nodes [OK]

Hint: Focus on sum of node values, not path length or count [OK]

Common Mistakes:

• Confusing path sum with path length
• Thinking path must start at root
• Ignoring negative values in nodes

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

easy

A. public void maxPathSum(TreeNode root) int

B. public int maxPathSum(TreeNode root)

C. int maxPathSum(TreeNode root) void

D. maxPathSum(TreeNode root) -> int

Solution

1. Step 1: Recall Java method syntax

   In Java, a method returning an int with public access and a parameter of type TreeNode is declared as: public int maxPathSum(TreeNode root).

2. Step 2: Check other options for syntax errors

   Options A, B, and D have invalid syntax: missing return type, misplaced void, or arrow notation not used in Java.

3. Final Answer:

   public int maxPathSum(TreeNode root) -> Option B

4. Quick Check:

   Java method syntax = public int methodName(Type param) [OK]

Hint: Remember Java method syntax: access returnType name(params) [OK]

Common Mistakes:

• Using arrow notation like other languages
• Mixing return type and void incorrectly
• Omitting access modifier

3. Given the following binary tree:

    1
   / \
  2   3

What is the maximum path sum?

medium

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Identify all possible paths and their sums

   Paths and sums: 2 alone = 2, 3 alone = 3, 1 alone = 1, 2->1 = 3, 3->1 = 4, 2->1->3 = 6.

2. Step 2: Find the maximum sum

   The maximum sum is 6 from path 2->1->3.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Sum(2+1+3) = 6 [OK]

Hint: Check sums including root and both children [OK]

Common Mistakes:

• Ignoring paths that go through root connecting both children
• Only considering single branches
• Adding node values incorrectly

4. Consider this Java method snippet for maximum path sum:

int maxPathSum(TreeNode root) {
  if (root == null) return 0;
  int left = maxPathSum(root.left);
  int right = maxPathSum(root.right);
  return Math.max(left, right) + root.val;
}

What is the main issue with this code?

medium

A. It uses Math.max instead of Math.min

B. It returns 0 for null nodes instead of Integer.MIN_VALUE

C. It does not consider paths passing through the root connecting left and right

D. It does not handle negative node values

Solution

1. Step 1: Analyze the recursive return value

   The code returns the max sum of either left or right subtree plus root value, ignoring the case where path passes through root connecting both sides.

2. Step 2: Understand maximum path sum definition

   Maximum path sum can include left subtree + root + right subtree, which this code misses.

3. Final Answer:

   It does not consider paths passing through the root connecting left and right -> Option C

4. Quick Check:

   Missing combined path sum through root [OK]

Hint: Remember max path can include both left and right subtrees [OK]

Common Mistakes:

• Ignoring combined paths through root
• Assuming max of left/right is enough
• Not updating global max path sum

5. You have a binary tree with nodes that can have negative values. Which approach correctly finds the maximum path sum?

hard

A. Use a recursive helper that returns max gain from each node, update global max with max of left + node + right, and ignore negative gains by comparing with 0

B. Sum all node values and return the total as maximum path sum

C. Only consider paths starting from root to leaf nodes

D. Use breadth-first search to find the longest path and sum its nodes

Solution

1. Step 1: Understand handling negative values

   Negative node values can reduce path sum, so ignore negative gains by comparing with 0 when calculating max gain from children.

2. Step 2: Use recursive helper with global max update

   Recursively compute max gain from left and right, update global max with left + node + right, and return max gain for parent calls.

3. Step 3: Reject incorrect approaches

   Summing all nodes ignores path constraints, root-to-leaf only misses other paths, BFS longest path ignores sums.

4. Final Answer:

   Use a recursive helper that returns max gain from each node, update global max with max of left + node + right, and ignore negative gains by comparing with 0 -> Option A

5. Quick Check:

   Recursive max gain + global max update handles negatives [OK]

Hint: Ignore negative gains by max(child, 0) in recursion [OK]

Common Mistakes:

• Summing all nodes regardless of path
• Only considering root-to-leaf paths
• Not handling negative values properly