Maximum Path Sum in Binary Tree in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the maximum path sum starting from the current node or 0 if negative.

DSA C#

int MaxGain(TreeNode node) {
    if (node == null) return 0;
    int leftGain = Math.Max(MaxGain(node.left), [1]);
    return node.val + leftGain;
}

Drag options to blanks, or click blank then click option'

Anode.val

B0

C-1

Dint.MinValue

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.val instead of 0 causes incorrect sums when child is negative.

Returning negative values decreases the path sum.

We use 0 to ignore negative gains from child nodes, so the path sum does not decrease.

2fill in blank

medium

Complete the code to update the global maximum path sum including the current node and both children.

DSA C#

int leftGain = Math.Max(MaxGain(node.left), 0);
int rightGain = Math.Max(MaxGain(node.right), 0);
int priceNewPath = node.val + leftGain + [1];
maxSum = Math.Max(maxSum, priceNewPath);

Drag options to blanks, or click blank then click option'

AleftGain

Bnode.val

CrightGain

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Adding node.val twice instead of rightGain.

Adding leftGain again instead of rightGain.

We add rightGain to include the maximum gain from the right child in the new path sum.

3fill in blank

hard

Fix the error in returning the maximum gain for recursion to parent node.

DSA C#

return node.val + Math.Max([1], rightGain);

Drag options to blanks, or click blank then click option'

AleftGain

Bnode.val

CmaxSum

DpriceNewPath

Attempts:

3 left

💡 Hint

Common Mistakes

Returning priceNewPath includes both children, which is invalid for recursion.

Returning maxSum is incorrect as it is a global variable.

We return the node value plus the maximum gain from either left or right child to continue the path upwards.

4fill in blank

hard

Fill both blanks to complete the recursive function that updates maxSum and returns max gain.

DSA C#

int MaxGain(TreeNode node) {
    if (node == null) return 0;
    int leftGain = Math.Max(MaxGain(node.left), [1]);
    int rightGain = Math.Max(MaxGain(node.right), [2]);
    int priceNewPath = node.val + leftGain + rightGain;
    maxSum = Math.Max(maxSum, priceNewPath);
    return node.val + Math.Max(leftGain, rightGain);
}

Drag options to blanks, or click blank then click option'

A0

Bnode.val

C-1

Dint.MinValue

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.val instead of 0 causes incorrect calculations.

Using negative values decreases the path sum.

We use 0 to ignore negative gains from both left and right children.

5fill in blank

hard

Fill all three blanks to complete the main function that initializes maxSum and calls MaxGain.

DSA C#

public int MaxPathSum(TreeNode root) {
    maxSum = [1];
    MaxGain([2]);
    return [3];
}

Drag options to blanks, or click blank then click option'

Aroot

Bint.MinValue

CmaxSum

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing maxSum to 0 causes wrong results if all nodes are negative.

Returning root instead of maxSum.

maxSum starts at int.MinValue to handle negative values; call MaxGain on root; return maxSum.

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