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

Concept Flow - Maximum Path Sum in Binary Tree

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 sum is higher

↓

Return max path sum including current node and one subtree

↓

Repeat for all nodes via recursion

↓

Final max path sum stored globally

The algorithm visits each node, calculates max path sums from left and right children, updates the global max path sum including the current node, and returns the max sum path extending to one child.

Execution Sample

DSA C++

int maxPathSum(TreeNode* root) {
  int maxSum = INT_MIN;
  maxGain(root, maxSum);
  return maxSum;
}

int maxGain(TreeNode* node, int &maxSum) {
  if (!node) return 0;
  int leftGain = max(maxGain(node->left, maxSum), 0);
  int rightGain = max(maxGain(node->right, maxSum), 0);
  int priceNewPath = node->val + leftGain + rightGain;
  maxSum = max(maxSum, priceNewPath);
  return node->val + max(leftGain, rightGain);
}

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

Execution Table

Step	Operation	Node Visited	Left Gain	Right Gain	Price New Path	Global Max Updated	Return Value	Visual State
1	Visit node	1 (root)	?	?	?	INT_MIN	?	1
2	Visit left child	2	?	?	?	INT_MIN	?	1 -> 2
3	Visit left child of 2	4	0	0	4	4	4	1 -> 2 -> 4
4	Return from 4	4	0	0	4	4	4	1 -> 2 -> 4
5	Visit right child of 2	5	0	0	5	5	5	1 -> 2 -> 4,5
6	Return from 5	5	0	0	5	5	5	1 -> 2 -> 4,5
7	Calculate at 2	2	4	5	11	11	7	1 -> 2 -> 4,5
8	Return from 2	2	4	5	11	11	7	1 -> 2 -> 4,5
9	Visit right child	3	?	?	?	11	?	1 -> 2 -> 4,5,3
10	Visit left child of 3	6	0	0	6	11	6	1 -> 2 -> 4,5,3,6
11	Return from 6	6	0	0	6	11	6	1 -> 2 -> 4,5,3,6
12	Visit right child of 3	7	0	0	7	11	7	1 -> 2 -> 4,5,3,6,7
13	Return from 7	7	0	0	7	11	7	1 -> 2 -> 4,5,3,6,7
14	Calculate at 3	3	6	7	16	16	10	1 -> 2 -> 4,5,3,6,7
15	Return from 3	3	6	7	16	16	10	1 -> 2 -> 4,5,3,6,7
16	Calculate at 1 (root)	1	7	10	18	18	11	1 -> 2 -> 4,5,3,6,7
17	Return from 1	1	7	10	18	18	11	1 -> 2 -> 4,5,3,6,7
18	End	-	-	-	-	18	-	Final max path sum = 18

💡 All nodes visited, recursion unwound, global max path sum is 18

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 10	After Step 12	After Step 14	After Step 16	Final
maxSum	INT_MIN	4	5	11	11	11	16	18	18
leftGain (node 2)	?	4	4	4	4	4	4	4	4
rightGain (node 2)	?	?	5	5	5	5	5	5	5
leftGain (node 3)	?	?	?	?	6	6	6	6	6
rightGain (node 3)	?	?	?	?	?	7	7	7	7
return value (node 1)	?	?	?	?	?	?	?	11	11

Key Moments - 3 Insights

Why do we take max with 0 for leftGain and rightGain?

Because negative gains would reduce the path sum, we ignore them by taking max with 0 as shown in steps 3, 5, 10, and 12 where gains are set to 0 if negative.

Why do we update the global max with priceNewPath instead of return value?

The global max considers the path through the current node including both children (step 7, 14, 16), but the return value only includes the node plus one child's max gain to maintain path continuity upwards.

What does the return value represent at each node?

It represents the maximum gain from the current node to one of its subtrees, used by the parent node to compute its path sums, as seen in steps 7, 14, and 16.

Visual Quiz - 3 Questions

Look at the execution table at step 14, what is the priceNewPath at node 3?

A 13

B 10

C 16

D 18

💡 Hint

Check the 'Price New Path' column at step 14 in the execution_table.

At which step does the global max first update to 11?

A Step 5

B Step 7

C Step 14

D Step 16

💡 Hint

Look at the 'Global Max Updated' column and find when it changes to 11.

If node 5 had a negative value, how would that affect the leftGain or rightGain at node 2?

A rightGain would be zero

B leftGain would be negative

C rightGain would be negative

D leftGain would be zero

💡 Hint

Recall that negative gains are replaced by zero as per the max with 0 rule in variable_tracker.

Concept Snapshot

Maximum Path Sum in Binary Tree:
- Visit each node recursively
- Calculate max gain from left and right children (ignore negatives)
- Update global max with node.val + leftGain + rightGain
- Return node.val + max(leftGain, rightGain) to parent
- Final global max is the answer

Full Transcript

The maximum path sum in a binary tree is found by visiting each node and calculating the maximum gain from its left and right children. Negative gains are ignored by taking the maximum with zero. At each node, the algorithm calculates the sum of the node's value plus the left and right gains, updating a global maximum if this sum is higher. The function returns the node's value plus the maximum gain from one child to maintain path continuity. This process repeats recursively for all nodes, and the global maximum path sum is returned at the end.

Practice

1. What does the term Maximum Path Sum in a binary tree mean?

easy

A. The sum of all node values in the tree

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

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

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

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

   It is the highest 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 in the tree -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking path must start at root
• Considering only leaf nodes for path ends

2. Which of the following C++ function signatures is correct for a helper function that returns the maximum path sum starting from a given node in a binary tree?

easy

A. int maxPathSumHelper(TreeNode* root, int& maxSum);

B. void maxPathSumHelper(TreeNode root, int maxSum);

C. int maxPathSumHelper(TreeNode root);

D. int maxPathSumHelper(TreeNode* root);

Solution

1. Step 1: Understand parameter passing

   The function needs to update maxSum globally, so it must be passed by reference.

2. Step 2: Check pointer usage

   TreeNode* is used to pass node pointers, not objects directly.

3. Final Answer:

   int maxPathSumHelper(TreeNode* root, int& maxSum); -> Option A

4. Quick Check:

   Use pointer and reference for maxSum [OK]

Hint: Pass maxSum by reference and node as pointer [OK]

Common Mistakes:

• Passing TreeNode by value instead of pointer
• Not passing maxSum by reference
• Using void return type instead of int

3. Consider the following binary tree:

    1
   / \
  2   3

What is the maximum path sum returned by the standard algorithm?

medium

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Calculate path sums including root

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

2. Step 2: Identify maximum sum

   The maximum path sum is 6 from path 2->1->3.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   2+1+3 = 6 [OK]

Hint: Check all paths including both children and root [OK]

Common Mistakes:

• Considering only root-to-leaf paths
• Ignoring paths passing through root
• Adding only one child value

4. Given this buggy code snippet for maximum path sum, what is the main error?

int maxPathSumHelper(TreeNode* root, int& maxSum) {
  if (!root) return 0;
  int left = maxPathSumHelper(root->left, maxSum);
  int right = maxPathSumHelper(root->right, maxSum);
  int current = root->val + left + right;
  maxSum = max(maxSum, current);
  return root->val + max(left, right);
}

What is the bug?

medium

A. It does not ignore negative path sums

B. It returns sum of both children instead of max child

C. It updates maxSum incorrectly

D. It does not handle null root

Solution

1. Step 1: Analyze negative path sums handling

   The code adds left and right directly without ignoring negative sums, which can reduce maxSum.

2. Step 2: Correct approach for negatives

   Should use max(0, left) and max(0, right) to ignore negative sums.

3. Final Answer:

   It does not ignore negative path sums -> Option A

4. Quick Check:

   Negative sums must be ignored to maximize path sum [OK]

Hint: Use max(0, child) to ignore negative sums [OK]

Common Mistakes:

• Adding negative child sums reduces maxSum
• Returning sum of both children instead of max child
• Not checking for null root

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

       -10
       /  \
      9   20
          / \
         15  7

Choose the correct maximum path sum.

hard

A. 27

B. 35

C. 42

D. 15

Solution

1. Step 1: Calculate max path sums for subtrees

   Left subtree max path sum is 9. Right subtree max path sum includes 20 + 15 + 7 = 42.

2. Step 2: Consider paths through root

   Path through root: -10 + max(0,9) + max(0,15+20+7) = -10 + 9 + 42 = 41, less than 42.

3. Step 3: Identify maximum path sum

   The maximum path sum is 42 from path 15->20->7.

4. Final Answer:

   42 -> Option C

5. Quick Check:

   15+20+7 = 42 [OK]

Hint: Check all subtree sums and paths through root [OK]

Common Mistakes:

• Including negative root value in max path sum
• Ignoring paths not passing through root
• Adding left and right children without max(0, val)