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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Path Sum Calculation

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

DSA C#

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

public class Solution {
    private int maxSum = int.MinValue;
    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);
    }
}

// Tree structure:
//       -10
//       /  \
//      9   20
//          / \
//         15  7

var root = new TreeNode(-10,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
var sol = new Solution();
System.Console.WriteLine(sol.MaxPathSum(root));

A 27

B 35

C 42

D 20

💡 Hint

Consider the path that includes the root's right subtree and both children of node 20.

The maximum path sum is 42, coming from the path 15 -> 20 -> 7, plus the root's value -10 is not included because it reduces the sum. The path 15 + 20 + 7 = 42 is the highest sum.

🧠 Conceptual

intermediate

Understanding Path Sum Constraints

In the Maximum Path Sum problem, which of the following statements is true about the paths considered?

A Paths can include nodes that are not connected directly.

B Paths must start at the root and end at a leaf node.

C Paths must include at least one leaf node.

D Paths can start and end at any nodes in the tree, but must be connected.

💡 Hint

Think about whether the path must start at the root or can be anywhere.

The maximum path sum can be any path in the tree that is connected, starting and ending at any nodes, not necessarily the root or leaf nodes.

🔧 Debug

advanced

Identify the Error in Maximum Path Sum Implementation

What error will the following C# code produce when trying to compute the maximum path sum?

DSA C#

public class Solution {
    private int maxSum = int.MinValue;
    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 Incorrect maximum path sum because negative gains are not ignored

B Correct output with no errors

C StackOverflowException due to infinite recursion

D NullReferenceException when node is null

💡 Hint

Consider how negative values in subtrees affect the path sum calculation.

The code does not ignore negative gains from left or right subtrees, which can reduce the path sum. This leads to incorrect maximum path sum calculation.

📝 Syntax

advanced

Syntax Error in Recursive Maximum Path Sum Function

Which option contains a syntax error in the C# recursive function for maximum path sum?

A

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

B

}
;)niaGthgir ,niaGtfel(xaM.htaM + lav.edon nruter    
;)htaPweNecirp ,muSxam(xaM.htaM = muSxam    
;niaGthgir + niaGtfel + lav.edon = htaPweNecirp tni    
;)0 ,)thgir.edon(niaGxaM(xaM.htaM = niaGthgir tni    
;)0 ,)tfel.edon(niaGxaM(xaM.htaM = niaGtfel tni    
;0 nruter )llun == edon( fi    
{ )edon edoNeerT(niaGxaM tni etavirp

C

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

D

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

💡 Hint

Check for missing semicolons in the code.

Option C is missing a semicolon after the return statement in the if condition, causing a syntax error.

🚀 Application

expert

Maximum Path Sum with Negative Values

Given the binary tree below, what is the maximum path sum? // Tree structure: // -2 // / \ // -1 -3 // / \ // -4 -5 Use the maximum path sum algorithm that ignores negative gains.

A -1

B -3

C -2

D 0

💡 Hint

The maximum path sum may be a single node if all paths have negative sums.

The maximum path sum is -1, which is the highest single node value in the tree. Since all paths have negative sums, the algorithm chooses the least negative node.

Practice

1. What does the term Maximum Path Sum in a binary tree mean?

easy

A. The largest sum of values along any path between two nodes in the tree

B. The sum of all node values in the tree

C. The sum of values from root to the deepest leaf only

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

Solution

1. Step 1: Understand the path definition

   A path in a binary tree can start and end at any nodes, not necessarily root or leaf.

2. Step 2: Define maximum path sum

   The maximum path sum is the highest sum of node values along any such path.

3. Final Answer:

   The largest sum of values along any path between two nodes in the tree -> Option A

4. Quick Check:

   Maximum path sum means highest sum on any path [OK]

Hint: Maximum path sum is any path with highest total value [OK]

Common Mistakes:

• Thinking path must start at root
• Confusing sum of all nodes with maximum path sum
• Assuming path must end at leaf

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

easy

A. public int MaxPathSum(TreeNode root)

B. int MaxPathSum(TreeNode root) void

C. public void MaxPathSum(TreeNode root) int

D. public int MaxPathSum() TreeNode root

Solution

1. Step 1: Check method return type and parameters

   The method should return an integer and accept a TreeNode parameter.

2. Step 2: Validate C# syntax

   Correct syntax is: access modifier + return type + method name + parameters in parentheses.

3. Final Answer:

   public int MaxPathSum(TreeNode root) -> Option A

4. Quick Check:

   Correct C# method signature syntax [OK]

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

Common Mistakes:

• Wrong return type placement
• Missing parentheses for parameters
• Incorrect order of return type and parameters

3. Given the following binary tree:

    1
   / \
  2   3

What is the maximum path sum?

medium

A. 5

B. 6

C. 3

D. 4

Solution

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

   Paths: 2->1->3 = 6, 1->2 = 3, 1->3 = 4, single nodes 1,2,3.

2. Step 2: Find the maximum sum

   The path 2->1->3 has sum 2+1+3 = 6, which is the highest.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Sum of path 2->1->3 = 6 [OK]

Hint: Check all paths including root and children [OK]

Common Mistakes:

• Only considering root to leaf paths
• Ignoring paths that go through root connecting two children
• Calculating sum of nodes incorrectly

4. Consider this C# code snippet for maximum path sum in a binary tree:

int maxSum = int.MinValue;
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);
}

What is the purpose of Math.Max(MaxGain(node.left), 0)?

medium

A. To reset maxSum to zero

B. To always add left subtree sum regardless of sign

C. To calculate the minimum path sum

D. To ignore negative path sums from left subtree

Solution

1. Step 1: Understand MaxGain return value

   MaxGain returns max path sum from subtree or 0 if negative.

2. Step 2: Purpose of Math.Max with 0

   This ensures negative sums are ignored, so path sum doesn't decrease.

3. Final Answer:

   To ignore negative path sums from left subtree -> Option D

4. Quick Check:

   Negative sums replaced by zero to avoid lowering total [OK]

Hint: Ignore negative sums by comparing with zero [OK]

Common Mistakes:

• Thinking it always adds left subtree sum
• Confusing maxSum update with this line
• Assuming it resets maxSum variable

5. You have a binary tree with nodes having values:

      -10
      /  \
     9   20
         /  \
        15   7

What is the maximum path sum in this tree?

hard

A. 27

B. 42

C. 35

D. 15

Solution

1. Step 1: Calculate path sums including left and right children

   Possible max path: 15 + 20 + 7 = 42, or 9 alone, or -10 + 9, etc.

2. Step 2: Identify maximum path sum

   The path 15->20->7 has sum 42, which is the highest possible.

3. Final Answer:

   35 -> Option C

4. Quick Check:

   Sum of 15 + 20 + 7 = 42 but max path includes -10 + 20 + 15 + 7 = 32, max path is 35 including 9 + 20 + 15 + 7

Hint: Check sums of subtrees and their combinations [OK]

Common Mistakes:

• Including negative root value in max path
• Only considering root-to-leaf paths
• Ignoring paths that skip root