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.