Maximum Path Sum in Binary Tree in DSA Java - 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

↓

Update global max if current path sum is higher

↓

Return max path sum for one side + current node

↓

Repeat for all nodes

↓

Final max path sum stored globally

Start from root, recursively find max path sums from left and right children, update global max with paths through current node, return max single-side path to parent.

Execution Sample

DSA Java

int maxSum = Integer.MIN_VALUE;

int maxPathSum(TreeNode root) {
  maxSum = Integer.MIN_VALUE;
  maxGain(root);
  return maxSum;
}

int maxGain(TreeNode node) {
  if (node == null) return 0;
  int leftGain = Math.max(maxGain(node.left), 0);
  int rightGain = Math.max(maxGain(node.right), 0);
  int priceNewPath = node.val + leftGain + rightGain;
  maxSum = Math.max(maxSum, priceNewPath);
  return node.val + Math.max(leftGain, rightGain);
}

Recursively compute max gain from each node, update global max path sum including both children and node, return max gain for one side.

Execution Table

Step	Operation	Node Visited	Left Gain	Right Gain	Price New Path	Global Max Updated	Return Value	Visual State
1	Visit leaf node	Node 15	0	0	15	maxSum = 15	15	15
2	Visit leaf node	Node 7	0	0	7	maxSum = 15	7	7
3	Visit node 20	Node 20	15	7	42	maxSum = 42	20 + max(15,7) = 35	20(15,7)
4	Visit leaf node	Node 9	0	0	9	maxSum = 42	9	9
5	Visit leaf node	Node 8	0	0	8	maxSum = 42	8	8
6	Visit node 3	Node 3	9	8	20	maxSum = 42	3 + max(9,8) = 12	3(9,8)
7	Visit root node	Node -10	35	12	37	maxSum = 42	-10 + max(35,12) = 25	-10(35,12)
8	End	All nodes visited	-	-	-	maxSum = 42	-	Final max path sum = 42

💡 All nodes visited, recursion ends, global maxSum holds maximum path sum

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
maxSum	-∞	15	15	42	42	42	42	42	42
leftGain (node 20)	-	-	-	15	-	-	-	-	-
rightGain (node 20)	-	-	-	7	-	-	-	-	-
leftGain (node 3)	-	-	-	-	-	-	9	-	-
rightGain (node 3)	-	-	-	-	-	-	8	-	-
return value (node 20)	-	-	-	35	-	-	-	-	-
return value (node 3)	-	-	-	-	-	-	12	-	-
return value (root)	-	-	-	-	-	-	-	25	-

Key Moments - 3 Insights

Why do we use Math.max(maxGain(node.left), 0) instead of just maxGain(node.left)?

Because negative gains would reduce the path sum, we ignore them by taking max with 0. See execution_table rows 1,2,4,5 where leftGain or rightGain is 0 if negative.

Why do we update the global maxSum with node.val + leftGain + rightGain?

This represents the max path sum passing through the current node including both children, which might be the overall max. See step 3 where maxSum updates to 42.

Why do we return node.val + max(leftGain, rightGain) instead of including both sides?

Because the path upwards to parent can only include one side to keep path valid (no forks). See return values in execution_table steps 3,6,7.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the global maxSum after visiting node 20?

A 15

B 35

C 42

D 22

💡 Hint

Check the 'Global Max Updated' column at step 3 in execution_table

At which step does the algorithm ignore negative gains by using max with 0?

A Step 1 and 2

B Step 4 and 5

C Step 7

D Step 8

💡 Hint

Look at 'Left Gain' and 'Right Gain' columns for leaf nodes in execution_table rows 4 and 5

If node 3 had a right child with value 10, how would the return value at step 6 change?

A It would increase to 13

B It would remain 12

C It would decrease

D It would become 22

💡 Hint

Return value is node.val + max(leftGain, rightGain). Adding a right child with value 10 increases rightGain.

Concept Snapshot

Maximum Path Sum in Binary Tree:
- Use recursion to find max gain from left and right children
- Ignore negative gains by max with 0
- Update global max with node.val + leftGain + rightGain
- Return node.val + max(leftGain, rightGain) to parent
- Final global maxSum is the answer

Full Transcript

This visualization traces the maximum path sum in a binary tree. Starting at the root, the algorithm recursively calculates the maximum gain from left and right subtrees, ignoring negative gains by taking the maximum with zero. At each node, it calculates the price of a new path including the node and both children, updating a global maximum if this is higher. The function returns the maximum gain including the node and one child to ensure the path remains valid. The execution table shows each step visiting nodes, gains calculated, global max updates, and return values. Key moments clarify why negative gains are ignored, why the global max includes both children, and why only one side is returned. The quiz tests understanding of these steps and their effects on the global maximum path sum.

Practice

1. What does the Maximum Path Sum in Binary Tree problem ask you to find?

easy

A. The highest sum of values along any path in the tree

B. The longest path length in the tree

C. The smallest value in the tree

D. The number of leaf nodes in the tree

Solution

1. Step 1: Understand the problem goal

   The problem asks for the maximum sum of node values along any path in the binary tree. A path can start and end at any node but must be connected.

2. Step 2: Differentiate from other tree metrics

   It is not about path length, smallest value, or leaf count. It focuses on sum of node values along a path.

3. Final Answer:

   The highest sum of values along any path in the tree -> Option A

4. Quick Check:

   Maximum path sum = highest sum of connected nodes [OK]

Hint: Focus on sum of node values, not path length or count [OK]

Common Mistakes:

• Confusing path sum with path length
• Thinking path must start at root
• Ignoring negative values in nodes

2. Which of the following Java method signatures is correct for a function that returns the maximum path sum in a binary tree node class TreeNode?

easy

A. public void maxPathSum(TreeNode root) int

B. public int maxPathSum(TreeNode root)

C. int maxPathSum(TreeNode root) void

D. maxPathSum(TreeNode root) -> int

Solution

1. Step 1: Recall Java method syntax

   In Java, a method returning an int with public access and a parameter of type TreeNode is declared as: public int maxPathSum(TreeNode root).

2. Step 2: Check other options for syntax errors

   Options A, B, and D have invalid syntax: missing return type, misplaced void, or arrow notation not used in Java.

3. Final Answer:

   public int maxPathSum(TreeNode root) -> Option B

4. Quick Check:

   Java method syntax = public int methodName(Type param) [OK]

Hint: Remember Java method syntax: access returnType name(params) [OK]

Common Mistakes:

• Using arrow notation like other languages
• Mixing return type and void incorrectly
• Omitting access modifier

3. Given the following binary tree:

    1
   / \
  2   3

What is the maximum path sum?

medium

A. 4

B. 5

C. 3

D. 6

Solution

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

   Paths and sums: 2 alone = 2, 3 alone = 3, 1 alone = 1, 2->1 = 3, 3->1 = 4, 2->1->3 = 6.

2. Step 2: Find the maximum sum

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

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Sum(2+1+3) = 6 [OK]

Hint: Check sums including root and both children [OK]

Common Mistakes:

• Ignoring paths that go through root connecting both children
• Only considering single branches
• Adding node values incorrectly

4. Consider this Java method snippet for maximum path sum:

int maxPathSum(TreeNode root) {
  if (root == null) return 0;
  int left = maxPathSum(root.left);
  int right = maxPathSum(root.right);
  return Math.max(left, right) + root.val;
}

What is the main issue with this code?

medium

A. It uses Math.max instead of Math.min

B. It returns 0 for null nodes instead of Integer.MIN_VALUE

C. It does not consider paths passing through the root connecting left and right

D. It does not handle negative node values

Solution

1. Step 1: Analyze the recursive return value

   The code returns the max sum of either left or right subtree plus root value, ignoring the case where path passes through root connecting both sides.

2. Step 2: Understand maximum path sum definition

   Maximum path sum can include left subtree + root + right subtree, which this code misses.

3. Final Answer:

   It does not consider paths passing through the root connecting left and right -> Option C

4. Quick Check:

   Missing combined path sum through root [OK]

Hint: Remember max path can include both left and right subtrees [OK]

Common Mistakes:

• Ignoring combined paths through root
• Assuming max of left/right is enough
• Not updating global max path sum

5. You have a binary tree with nodes that can have negative values. Which approach correctly finds the maximum path sum?

hard

A. Use a recursive helper that returns max gain from each node, update global max with max of left + node + right, and ignore negative gains by comparing with 0

B. Sum all node values and return the total as maximum path sum

C. Only consider paths starting from root to leaf nodes

D. Use breadth-first search to find the longest path and sum its nodes

Solution

1. Step 1: Understand handling negative values

   Negative node values can reduce path sum, so ignore negative gains by comparing with 0 when calculating max gain from children.

2. Step 2: Use recursive helper with global max update

   Recursively compute max gain from left and right, update global max with left + node + right, and return max gain for parent calls.

3. Step 3: Reject incorrect approaches

   Summing all nodes ignores path constraints, root-to-leaf only misses other paths, BFS longest path ignores sums.

4. Final Answer:

   Use a recursive helper that returns max gain from each node, update global max with max of left + node + right, and ignore negative gains by comparing with 0 -> Option A

5. Quick Check:

   Recursive max gain + global max update handles negatives [OK]

Hint: Ignore negative gains by max(child, 0) in recursion [OK]

Common Mistakes:

• Summing all nodes regardless of path
• Only considering root-to-leaf paths
• Not handling negative values properly