Maximum Path Sum in Binary Tree in DSA C# - Execution Trace

Concept Flow - Maximum Path Sum in Binary Tree

Start at root node

↓

Calculate max path sum from left subtree

↓

Calculate max path sum from right subtree

↓

Calculate max path including current node and both children

↓

Update global max if current path sum is greater

↓

Return max path sum including current node and one child

↓

Repeat for all nodes via recursion

↓

Final global max is the answer

We recursively calculate max path sums from left and right children, update global max with paths through current node, and return max single path sum up to parent.

Execution Sample

DSA C#

int MaxPathSum(TreeNode root) {
  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);
  }
  MaxGain(root);
  return maxSum;
}

This code finds the maximum path sum in a binary tree by recursively calculating max gains from children and updating a global max.

Execution Table

Step	Operation	Node Visited	Left Gain	Right Gain	Price New Path	Global Max	Return Value	Visual State
1	Visit leaf node 15	15	0	0	15	15	15	Node(15)
2	Visit leaf node 7	7	0	0	7	15	7	Node(7)
3	Visit node 20	20	15	7	42	42	35	Node(20) -> Left(15), Right(7)
4	Visit leaf node 9	9	0	0	9	42	9	Node(9)
5	Visit leaf node 8	8	0	0	8	42	8	Node(8)
6	Visit node 3	3	9	8	20	42	12	Node(3) -> Left(9), Right(8)
7	Visit root node -10	-10	35	12	37	42	25	Node(-10) -> Left(20), Right(3)
8	End	None	N/A	N/A	N/A	42	42	Final max path sum

💡 All nodes visited, recursion ends, global max is final answer

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
maxSum	-∞	15	15	42	42	42	42	42	42
leftGain (node 20)	N/A	N/A	15	N/A	N/A	N/A	N/A	N/A	N/A
rightGain (node 20)	N/A	N/A	7	N/A	N/A	N/A	N/A	N/A	N/A
leftGain (node 3)	N/A	N/A	N/A	N/A	9	N/A	N/A	N/A	N/A
rightGain (node 3)	N/A	N/A	N/A	N/A	8	N/A	N/A	N/A	N/A
return value (node 20)	N/A	N/A	35	N/A	N/A	N/A	N/A	N/A	N/A
return value (node 3)	N/A	N/A	N/A	N/A	12	N/A	N/A	N/A	N/A
return value (root -10)	N/A	N/A	N/A	N/A	N/A	N/A	25	N/A	25

Key Moments - 3 Insights

Why do we use Math.Max with 0 for leftGain and rightGain?

Because negative gains would reduce the path sum, we ignore them by taking max with 0. See execution_table rows 1 and 2 where gains are 0 if negative.

Why do we update global max with node.val + leftGain + rightGain?

This represents the max path passing through the current node including both children, which might be the max path overall. See step 3 where priceNewPath is 42 updating maxSum.

Why do we return node.val + max(leftGain, rightGain) instead of sum of both?

Because when returning to parent, path must be a single branch (not split), so we choose the larger gain side. See return values in steps 3 and 6.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the global max after visiting node 20?

A 15

B 42

C 35

D 7

💡 Hint

Check the 'Global Max' column at step 3 in execution_table

At which step does the recursion return the value 12?

A Step 6

B Step 4

C Step 2

D Step 7

💡 Hint

Look at the 'Return Value' column in execution_table for step 6

If node 15 had a negative value, how would leftGain for node 20 change?

A It would become negative

B It would remain 15

C It would be zero

D It would be the sum of left and right gains

💡 Hint

Recall we take max of gain and 0, so negative values become 0 (see key_moments)

Concept Snapshot

Maximum Path Sum in Binary Tree:
- Use recursion to find max gain from left and right children
- Ignore negative gains by max with 0
- Update global max with node.val + leftGain + rightGain
- Return node.val + max(leftGain, rightGain) to parent
- Final global max is the answer

Full Transcript

This concept finds the maximum path sum in a binary tree by visiting each node recursively. At each node, it calculates the maximum gain from the left and right children, ignoring negative gains by taking the maximum with zero. It then calculates the price of a new path passing through the current node by summing the node's value and both gains. This price updates a global maximum if it is larger. The function returns the node's value plus the larger gain to the parent, ensuring the path is a single branch. The recursion continues until all nodes are visited, and the global maximum is returned as the maximum path sum.

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