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

Traverse each node recursively, compute max path sums from left and right children, update global max with path through current node, and return max path sum including one child.

Execution Sample

DSA C

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

Recursively computes max path sums from children, updates global max, and returns max sum including one child.

Execution Table

Step	Operation	Node Visited	Left Max	Right Max	Current Path Sum	Global Max	Return Value	Visual State
1	Visit leaf node	Node 4	0	0	4	4	4	4
2	Visit leaf node	Node 5	0	0	5	5	5	5
3	Visit node 2	Node 2	4	5	11	11	9	2(9) -> 4,5
4	Visit leaf node	Node 3	0	0	-3	11	0	3(0)
5	Visit root node	Node 1	9	0	10	11	10	1(10) -> 2(9),3(0)
6	End	-	-	-	-	11	-	Max path sum is 11

💡 All nodes visited, recursion unwound, global max updated to 11

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
maxSum	-inf	4	5	11	11	11	11
left	-	0	0	4	0	9	-
right	-	0	0	5	0	0	-
return	-	4	5	9	0	10	-

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 execution_table rows 1 and 4 where negative or zero values are replaced by 0.

Why does the function return max(left, right) + node->val instead of left + right + node->val?

Return value represents max path sum including current node and only one child to continue path upwards. The sum of left + right + node->val is used only to update global max for paths passing through the node. See execution_table row 3 and 5.

How is the global max updated during recursion?

At each node, global max is updated with left + right + node->val if it is greater than current global max. This captures paths passing through the node connecting left and right subtrees. See execution_table rows 3 and 5.

Visual Quiz - 3 Questions

Look at the execution_table, what is the global max after visiting node 2?

A 11

B 5

C 4

D 7

💡 Hint

Check the Global Max column at Step 3 in execution_table

At which step does the function return 0 for a node?

A Step 1

B Step 5

C Step 4

D Step 3

💡 Hint

Look at the Return Value column in execution_table for zero values

If node 3 had value 2 instead of -3, how would the global max change at step 5?

A It would remain 11

B It would increase

C It would decrease

D It would become 0

💡 Hint

Consider how positive right max affects Current Path Sum and Global Max at Step 5

Concept Snapshot

Maximum Path Sum in Binary Tree:
- Traverse tree recursively
- At each node, compute max(0, left) and max(0, right)
- Update global max with left + right + node value
- Return max(left, right) + node value
- Final global max is max path sum anywhere in tree

Full Transcript

This concept finds the maximum path sum in a binary tree by visiting each node recursively. For each node, it calculates the maximum path sum from its left and right children, ignoring negative sums by taking max with zero. It then updates a global maximum if the sum of left max, right max, and the node's value is greater than the current global max. The function returns the maximum path sum including the current node and one child to allow paths to continue upwards. The process repeats for all nodes, and the global max at the end is the maximum path sum in the tree.

Practice

1. What does the "maximum path sum" in a binary tree represent?

easy

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

B. The sum of all node values in the tree

C. The largest sum of values along any path between two nodes

D. The sum of values from root to the deepest leaf only

Solution

1. Step 1: Understand the path definition

   The path can start and end at any two nodes, not necessarily root or leaf.

2. Step 2: Identify maximum sum meaning

   It is the largest sum of node values along any such path in the tree.

3. Final Answer:

   The largest sum of values along any path between two nodes -> Option C

4. Quick Check:

   Maximum path sum means largest sum on any path [OK]

Hint: Maximum path sum is any path, not just root to leaf [OK]

Common Mistakes:

• Thinking it must start at root
• Confusing with sum of all nodes
• Considering only leaf nodes

2. Which of the following C function signatures is correct for a recursive function to find maximum path sum in a binary tree node defined as struct TreeNode?

easy

A. int maxPathSum(struct TreeNode* root);

B. void maxPathSum(struct TreeNode root);

C. int maxPathSum(struct TreeNode root);

D. int maxPathSum(struct TreeNode** root);

Solution

1. Step 1: Understand parameter passing for trees in C

   Binary trees are usually passed as pointers to nodes, so struct TreeNode* is correct.

2. Step 2: Check return type and parameter correctness

   Function returns int (maximum sum), and parameter is pointer to root node, so int maxPathSum(struct TreeNode* root); is correct.

3. Final Answer:

   int maxPathSum(struct TreeNode* root); -> Option A

4. Quick Check:

   Use pointer parameter and int return type [OK]

Hint: Use pointer to struct for tree nodes in C functions [OK]

Common Mistakes:

• Passing struct by value instead of pointer
• Using void return type instead of int
• Using double pointer unnecessarily

3. Given the binary tree below, what is the maximum path sum?

    1
   / \
  2   3

medium

A. 5

B. 6

C. 4

D. 3

Solution

1. Step 1: Identify all possible paths and their sums

   Paths: 2->1->3 sum = 6, 1->2 sum = 3, 1->3 sum = 4, single nodes 2,3,1.

2. Step 2: Find the maximum sum among these paths

   Maximum sum is 6 from path 2->1->3.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Sum of 2 + 1 + 3 = 6 [OK]

Hint: Check paths through root connecting left and right [OK]

Common Mistakes:

• Considering only root to leaf paths
• Ignoring paths that go through root connecting children
• Choosing max node value instead of path sum

4. Consider this buggy C code snippet for maximum path sum calculation:

int maxPathSumUtil(struct TreeNode* root, int* maxSum) {
    if (!root) return 0;
    int left = maxPathSumUtil(root->left, maxSum);
    int right = maxPathSumUtil(root->right, maxSum);
    int maxSingle = max(max(left, right) + root->val, root->val);
    int maxTop = max(maxSingle, left + right + root->val);
    *maxSum = max(*maxSum, maxTop);
    return maxSingle;
}

What is the main bug in this code?

medium

A. It does not update maxSum pointer correctly

B. It does not handle negative node values correctly

C. It returns maxTop instead of maxSingle

D. It uses max function without defining it

Solution

1. Step 1: Check usage of max function

   The code uses max() but C standard library does not have max function by default; it must be defined or replaced.

2. Step 2: Verify other logic parts

   Return and pointer update logic is correct; negative values handled by max comparisons.

3. Final Answer:

   It uses max function without defining it -> Option D

4. Quick Check:

   max() must be defined or replaced in C [OK]

Hint: Remember C has no built-in max function [OK]

Common Mistakes:

• Assuming max() is built-in in C
• Confusing return values with maxSum update
• Ignoring pointer usage correctness

5. You want to find the maximum path sum in a binary tree where some nodes have negative values. Which approach correctly handles negative values to find the maximum path sum?

hard

A. Use recursion to compute max path sums including negative values and update global max accordingly

B. Calculate sum of all nodes and subtract minimum negative node value

C. Only consider paths that include positive nodes and skip negative nodes completely

D. Ignore negative values by treating them as zero during recursion

Solution

1. Step 1: Understand handling of negative values in max path sum

   Negative values can reduce path sums, so recursion must consider them but choose max sums carefully.

2. Step 2: Use recursion with max comparisons to update global max

   Recursion returns max single path sum including negative values, updating global max with max of left+right+node or single path sums.

3. Final Answer:

   Use recursion to compute max path sums including negative values and update global max accordingly -> Option A

4. Quick Check:

   Include negatives but choose max sums carefully [OK]

Hint: Include negatives but pick max sums in recursion [OK]

Common Mistakes:

• Ignoring negative nodes completely
• Treating negatives as zero forcibly
• Using simple sums without max comparisons