DP on Trees Maximum Path Sum in DSA C# - Execution Trace

Concept Flow - DP on Trees Maximum Path Sum

Start at root node

↓

Compute max path sum from left subtree

↓

Compute max path sum from right subtree

↓

Calculate max path through current node

↓

Update global max if current path is higher

↓

Return max path sum including current node to parent

↓

Repeat for all nodes

↓

Final max path sum is global max

We start from the root and recursively compute max path sums from left and right children. At each node, we update the global max path sum considering paths through that node. We return the max path sum including the node to its parent.

Execution Sample

DSA C#

int MaxPathSum(TreeNode node) {
  if (node == null) return 0;
  int left = Math.Max(0, MaxPathSum(node.left));
  int right = Math.Max(0, MaxPathSum(node.right));
  globalMax = Math.Max(globalMax, left + right + node.val);
  return Math.Max(left, right) + node.val;
}

This code recursively computes max path sums from children, updates global max, and returns max path sum including current node.

Execution Table

Step	Operation	Node Visited	Left Max	Right Max	Current Max Path	Global Max	Return Value	Visual State
1	Visit node	3	0	0	3	3	3	3
2	Visit node	2	0	0	2	3	2	3 -> 2
3	Visit node	1	0	0	1	3	1	3 -> 2 -> 1
4	Return to node 2	2	0	1	3	3	3	3 -> 2 -> 1
5	Return to node 3	3	3	0	6	6	6	3 -> 2 -> 1
6	Visit node	4	0	0	4	6	4	3 -> 2 -> 1, 4
7	Visit node	5	0	0	5	6	5	3 -> 2 -> 1, 4 -> 5
8	Return to node 4	4	0	5	9	9	9	3 -> 2 -> 1, 4 -> 5
9	Return to node 3	3	3	9	15	15	12	3 -> 2 -> 1, 4 -> 5
10	End	null	-	-	-	15	-	Final max path sum = 15

💡 All nodes visited, global max path sum found as 15

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 8	After Step 9	Final
globalMax	-∞	3	3	6	9	15	15
Return Value (node 1)	-	1	1	1	1	1	1
Return Value (node 2)	-	-	3	3	3	3	3
Return Value (node 3)	-	-	-	6	6	12	12
Return Value (node 4)	-	-	-	-	9	9	9
Return Value (node 5)	-	-	-	-	5	5	5

Key Moments - 3 Insights

Why do we use Math.Max(0, childMax) when calculating left and right max?

Because negative path sums reduce the total, we ignore them by taking max with 0. See execution_table rows 1, 2, and 3 where left and right max are 0 when child returns negative or zero.

Why do we update globalMax with left + right + node.val instead of just max(left, right) + node.val?

Because the max path can pass through the current node connecting left and right subtrees. This is shown in execution_table row 9 where globalMax updates to 15 using left=3, right=9, and node.val=3.

What does the return value represent at each node?

It represents the max path sum including the current node and one of its subtrees to be used by its parent. This is why we return Math.Max(left, right) + node.val, as seen in variable_tracker for return values.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5. What is the globalMax value after visiting node 3?

A 9

B 3

C 6

D 15

💡 Hint

Check the 'Global Max' column at Step 5 in execution_table.

At which step does the globalMax first update to a value greater than 9?

A Step 6

B Step 9

C Step 8

D Step 7

💡 Hint

Look at the 'Global Max' column in execution_table rows 8 and 9.

If we did not use Math.Max(0, childMax), how would the return value for node 1 change at Step 3?

A It could be negative if node 1 had negative value

B It would always be zero

C It would be the same as 1

D It would be the sum of left and right child

💡 Hint

Refer to key_moments about ignoring negative sums and variable_tracker return values.

Concept Snapshot

DP on Trees Maximum Path Sum:
- Recursively compute max path sums from left and right children
- Use max(0, childSum) to ignore negative paths
- Update global max with left + right + node value
- Return max path including node and one child
- Final answer is global max after all nodes processed

Full Transcript

This visualization shows how to find the maximum path sum in a binary tree using dynamic programming. Starting from the root, we recursively calculate the maximum path sums from the left and right children. We ignore negative sums by taking the maximum of zero and the child's max path sum. At each node, we calculate the maximum path sum passing through it by adding the node's value and the left and right max sums. We update a global maximum if this sum is higher than the current global max. The function returns the maximum path sum including the current node and one of its children to be used by its parent. The process continues until all nodes are visited, and the global maximum holds the maximum path sum in the tree.

Practice

1. What does the "maximum path sum" in a tree represent in the context of DP on Trees Maximum Path Sum?

easy

A. The sum of all node values in the tree

B. The largest sum of node values on any path between two nodes in the tree

C. The maximum value of a single node in the tree

D. The longest path length in terms of number of edges

Solution

1. Step 1: Understand the problem definition

   The maximum path sum means the highest total sum of node values collected along any path connecting two nodes in the tree, not necessarily passing through the root.

2. Step 2: Differentiate from other sums

   It is not the sum of all nodes or just the maximum single node value, but the sum along a path that can include multiple nodes.

3. Final Answer:

   The largest sum of node values on any path between two nodes in the tree -> Option B

4. Quick Check:

   Maximum path sum = largest node value sum on any path [OK]

Hint: Maximum path sum is about sums along paths, not single nodes [OK]

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking it is just the maximum node value
• Assuming path must start at root

2. Which of the following C# method signatures is correct for a recursive function that returns the maximum path sum starting from a given tree node?

easy

A. int MaxPathSum(TreeNode node)

B. void MaxPathSum(TreeNode node)

C. int MaxPathSum(int node)

D. TreeNode MaxPathSum(TreeNode node)

Solution

1. Step 1: Identify the return type needed

   The function should return an integer representing the maximum path sum starting from the given node.

2. Step 2: Check parameter type

   The parameter must be a TreeNode object to access node values and children.

3. Final Answer:

   int MaxPathSum(TreeNode node) -> Option A

4. Quick Check:

   Return type int and parameter TreeNode required [OK]

Hint: Return int for sums, input parameter must be TreeNode [OK]

Common Mistakes:

• Using void return type when int is needed
• Passing int instead of TreeNode as parameter
• Returning TreeNode instead of int

3. Consider the following C# code snippet for a binary tree node class and a method to find maximum path sum:

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

int maxSum = int.MinValue;

int MaxPathSum(TreeNode node) {
    if (node == null) return 0;
    int left = Math.Max(0, MaxPathSum(node.left));
    int right = Math.Max(0, MaxPathSum(node.right));
    maxSum = Math.Max(maxSum, left + right + node.val);
    return Math.Max(left, right) + node.val;
}

// Tree structure:
//       1
//      / \
//     2   3

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
MaxPathSum(root);
Console.WriteLine(maxSum);

What is the output printed?

medium

A. 1

B. 5

C. 3

D. 6

Solution

1. Step 1: Calculate max path sums for children

   For node 2 and 3, left and right children are null, so returns 0. Max path sum at node 2 and 3 is their own value (2 and 3).

2. Step 2: Calculate max path sum at root

   At root (1), left = max(0, 2) = 2, right = max(0, 3) = 3. maxSum updated to max(-∞, 2+3+1) = 6. Return max(2,3)+1=4.

3. Final Answer:

   6 -> Option D

4. Quick Check:

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

Hint: Add left + right + node.val for max path at each node [OK]

Common Mistakes:

• Ignoring max(0, child) and using negative sums
• Returning sum without updating maxSum
• Confusing return value with maxSum

4. The following C# code attempts to compute the maximum path sum in a binary tree but has a bug:

int maxSum = int.MinValue;

int MaxPathSum(TreeNode node) {
    if (node == null) return 0;
    int left = MaxPathSum(node.left);
    int right = MaxPathSum(node.right);
    maxSum = Math.Max(maxSum, left + right + node.val);
    return Math.Max(left, right) + node.val;
}

What is the bug in this code?

medium

A. It does not ignore negative sums from children

B. It returns the wrong value type

C. It does not update maxSum correctly

D. It does not handle null nodes

Solution

1. Step 1: Analyze child sums usage

   The code uses left and right sums directly without ignoring negative values, which can reduce the path sum.

2. Step 2: Identify fix for negative sums

   We must use Math.Max(0, left) and Math.Max(0, right) to ignore negative sums from children.

3. Final Answer:

   It does not ignore negative sums from children -> Option A

4. Quick Check:

   Negative child sums must be ignored [OK]

Hint: Use Math.Max(0, childSum) to ignore negatives [OK]

Common Mistakes:

• Not using Math.Max(0, child) causing wrong sums
• Assuming return type is wrong
• Missing null checks (which are present)

5. Given a binary tree where some nodes have negative values, which approach correctly computes the maximum path sum using DP on trees? A) At each node, compute max path sum including both children and update global max; return max path sum including one child plus node value. B) At each node, sum all child node values and return total sum. C) At each node, return the maximum child value only. D) At each node, ignore children and consider only node value.

hard

A. Return the maximum child value only

B. Sum all child node values and return total sum

C. Compute max path sum including both children and update global max; return max path sum including one child plus node value

D. Ignore children and consider only node value

Solution

1. Step 1: Understand the correct DP approach

   The correct approach is to consider the maximum path sum including both children and update a global max, returning the max path sum including one child plus node value.

2. Step 2: Identify the incorrect options

   The other options do not correctly handle the problem. They either sum all children, return only the maximum child value, or ignore children and consider only node value.

3. Final Answer:

   Compute max path sum including both children and update global max; return max path sum including one child plus node value -> Option C

4. Quick Check:

   Correct DP uses both children sums and global max update [OK]

Hint: Include both children sums and update global max [OK]

Common Mistakes:

• Ignoring children nodes in calculation
• Summing all children without max checks
• Returning only child values without node