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 better

↓

Return max path sum including current node and one subtree

↓

Repeat for all nodes

↓

Final global max is answer

We start at 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.

Execution Sample

DSA C

int maxPathSumUtil(Node* node, int* globalMax) {
  if (!node) return 0;
  int left = max(0, maxPathSumUtil(node->left, globalMax));
  int right = max(0, maxPathSumUtil(node->right, globalMax));
  *globalMax = max(*globalMax, left + right + node->val);
  return node->val + max(left, right);
}

This function computes max path sum including current node and updates global max path sum.

Execution Table

Step	Operation	Node Visited	Left Max	Right Max	Current Max Path	Global Max Updated	Return Value	Visual State
1	Visit	Node 1 (val=1)	0	0	1	1	1	1
2	Visit	Node 2 (val=2)	0	0	2	2	2	1 -> 2
3	Visit	Node 4 (val=4)	0	0	4	4	4	1 -> 2 -> 4
4	Return	Node 4	0	0	4	4	4	1 -> 2 -> 4
5	Return	Node 2	4	0	6	6	6	1 -> 2 -> 4
6	Visit	Node 3 (val=3)	0	0	3	6	3	1 -> 2 -> 4, 3
7	Return	Node 3	0	0	3	6	3	1 -> 2 -> 4, 3
8	Return	Node 1	6	3	10	10	7	1 -> 2 -> 4, 3
9	End	-	-	-	-	-	-	Final max path sum = 10

💡 All nodes visited, global max path sum found

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	After Step 6	After Step 8	Final
globalMax	-inf	1	2	4	6	6	10	10
Return Value (Node 4)	-	-	-	4	-	-	-	4
Return Value (Node 2)	-	-	-	-	6	-	-	6
Return Value (Node 3)	-	-	-	-	-	3	-	3
Return Value (Node 1)	-	-	-	-	-	-	7	7

Key Moments - 3 Insights

Why do we take max(0, left) and max(0, right) instead of just left and right?

Because negative path sums reduce the total, we ignore them by taking max with 0. See steps 3 and 6 where left or right max is 0 if subtree sum is negative.

Why do we update global max with left + right + node value?

Because the max path can pass through the current node connecting left and right subtrees. This is shown in step 8 where global max updates to 10.

Why does the function return node value plus max(left, right) instead of left + right + node value?

Because when returning to parent, path can only extend through one child, not both. The sum of both sides is only for updating global max, not for return value (see step 8 return value 7).

Visual Quiz - 3 Questions

Look at the execution table, what is the global max after visiting Node 4?

A 4

B 2

C 1

D 6

💡 Hint

Check the 'Global Max Updated' column at step 4 in the execution table.

At which step does the global max path sum become 10?

A Step 6

B Step 8

C Step 5

D Step 3

💡 Hint

Look at the 'Global Max Updated' column and find when it reaches 10.

If Node 3 had a negative value, how would the return value at Node 1 change?

A It would increase

B It would stay the same

C It would decrease

D It would become zero

💡 Hint

Check the 'Return Value' column for Node 1 and consider how a negative right max affects it.

Concept Snapshot

DP on Trees Maximum Path Sum:
- Use recursion to get max path sums from left and right children
- Ignore negative sums by max(0, childSum)
- Update global max with left + right + node value
- Return node value + max(left, right) to parent
- Final global max is the answer

Full Transcript

This concept shows how to find the maximum path sum in a tree using dynamic programming. We start at the root and recursively compute the maximum path sums from left and right subtrees. At each node, we calculate the maximum path sum passing through it by adding the node's value and the maximum sums from left and right children, ignoring negative sums. We update a global maximum if this path is better. The function returns the maximum sum including the current node and one subtree to its parent. This 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 dynamic programming on trees?

easy

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

B. The number of nodes in the longest path of the tree

C. The sum of all node values in the tree

D. The height of the tree

Solution

1. Step 1: Understand the problem definition

   The maximum path sum is about finding the path between any two nodes that yields the highest sum of node values.

2. Step 2: Differentiate from other tree properties

   Unlike longest path or height, maximum path sum focuses on the sum of node values, not count or depth.

3. Final Answer:

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

4. Quick Check:

   Maximum path sum = largest node value sum [OK]

Hint: Maximum path sum is about sums, not counts or heights [OK]

Common Mistakes:

• Confusing maximum path sum with longest path length
• Thinking it is the sum of all nodes
• Mixing it up with tree height

2. Which of the following is the correct base case initialization for a recursive function computing maximum path sum in a binary tree node in C?

easy

A. if (node == NULL) return INT_MIN;

B. if (node == NULL) return -1;

C. if (node == NULL) return 1;

D. if (node == NULL) return 0;

Solution

1. Step 1: Understand base case for null nodes

   For maximum path sum, null nodes should contribute 0 to the path sum as they do not add any value.

2. Step 2: Choose appropriate return value

   Returning 0 ensures that null nodes do not affect the sum and allows the recursion to proceed correctly.

3. Final Answer:

   if (node == NULL) return 0; -> Option D

4. Quick Check:

   Base case returns 0 to represent no contribution from null nodes [OK]

Hint: Use 0 for null nodes to avoid affecting sums [OK]

Common Mistakes:

• Returning INT_MIN which can cause incorrect sums
• Returning positive values for null nodes
• Returning 1 or -1 which are arbitrary and incorrect

3. Consider the following C code snippet for maximum path sum in a binary tree node structure. What is the output printed by printf("%d", maxSum); after calling maxPathSum(root); on the tree below?

Tree structure:
1
/ \\
2 3

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

int maxSum = INT_MIN;

int maxPathSumUtil(Node* root) {
    if (!root) return 0;
    int left = maxPathSumUtil(root->left);
    int right = maxPathSumUtil(root->right);
    int maxSingle = (left > right ? left : right) + root->val;
    int maxTop = (left + right + root->val);
    if (maxTop > maxSum) maxSum = maxTop;
    return maxSingle > root->val ? maxSingle : root->val;
}

int maxPathSum(Node* root) {
    maxSum = INT_MIN;
    maxPathSumUtil(root);
    return maxSum;
}

medium

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Calculate max path sums for each node

   For node 2 and 3, maxSingle = 2 and 3 respectively, maxTop = 2 and 3. For root 1, left=2, right=3, maxSingle = max(2,3)+1=4, maxTop=2+3+1=6.

2. Step 2: Update maxSum and return final value

   maxSum updates to 6 at root. The function returns maxSum = 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

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

Hint: Sum path through root and children for max sum [OK]

Common Mistakes:

• Ignoring path through both children
• Returning maxSingle instead of maxSum
• Not updating global maxSum correctly

4. The following code attempts to compute the maximum path sum in a binary tree but has a bug. What is the bug?

int maxSum = INT_MIN;

int maxPathSumUtil(Node* root) {
    if (!root) return 0;
    int left = maxPathSumUtil(root->left);
    int right = maxPathSumUtil(root->right);
    int maxSingle = (left > right ? left : right) + root->val;
    int maxTop = (left + right + root->val);
    if (maxSingle > maxSum) maxSum = maxSingle;
    if (maxTop > maxSum) maxSum = maxTop;
    return maxSingle;
}

medium

A. It returns maxSingle without comparing it to root->val

B. It updates maxSum with maxSingle before maxTop, missing some max sums

C. It does not handle negative node values correctly

D. It returns maxSingle but should return maxTop

Solution

1. Step 1: Check return value correctness

   maxSingle should be max of (maxSingle, root->val) to handle negative values properly.

2. Step 2: Identify missing max comparison

   Without comparing maxSingle to root->val, the function may return a smaller sum than root's value alone.

3. Final Answer:

   It returns maxSingle without comparing it to root->val -> Option A

4. Quick Check:

   Return value must consider root->val for negatives [OK]

Hint: Always compare maxSingle with root->val before returning [OK]

Common Mistakes:

• Not handling negative values correctly
• Updating maxSum incorrectly
• Returning maxTop instead of maxSingle

5. Given a binary tree where nodes can have negative values, which approach correctly computes the maximum path sum using dynamic programming on trees?

hard

A. Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with zero

B. Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with the node's value itself

C. Use a recursive function that returns the sum of all nodes in the subtree, ignoring negative values, and update global max accordingly

D. Use a recursive function that returns the maximum path sum including the current node and both children always, without any comparison for negative values

Solution

1. Step 1: Understand handling of negative values

   Negative values require comparing max sums with the node's own value to avoid reducing sums by adding negative children.

2. Step 2: Correct recursive approach

   Return max path sum including current node and one child or node alone; update global max with sum of node and both children.

3. Final Answer:

   Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with the node's value itself -> Option B

4. Quick Check:

   Compare with node value to handle negatives correctly [OK]

Hint: Compare sums with node value itself to handle negatives [OK]

Common Mistakes:

• Ignoring negative values in sums
• Always adding both children without max checks
• Ignoring node's own value in comparisons