DP on Trees Maximum Path Sum in DSA Java - Execution Trace

Concept Flow - DP on Trees Maximum Path Sum

Start at root node

↓

Recursively find max path sum from left subtree

↓

Recursively find max path sum from right subtree

↓

Calculate max path through current node: left + node + right

↓

Update global max if current path is higher

↓

Return max path sum including current node and one subtree

↓

Repeat for all nodes

↓

Final max path sum stored globally

We start from the root and recursively find the max path sums from left and right subtrees. At each node, we calculate the max path sum passing through it and update the global max. We return the max sum including the node and one subtree to parent.

Execution Sample

DSA Java

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int v) { val = v; }
}

int maxSum = Integer.MIN_VALUE;

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

This code finds the maximum path sum in a binary tree by recursively calculating max sums from left and right children, updating a global max, and returning the max path including the current node.

Execution Table

Step	Operation	Node Visited	Left Max Path	Right Max Path	Current Max Path	Global Max Updated	Return Value	Visual State
1	Visit node	1	0	0	1	1	1	Node 1 (val=1)
2	Visit node	2	0	0	2	2	2	Node 2 (val=2)
3	Visit node	4	0	0	4	4	4	Node 4 (val=4)
4	Return to node	2	4	0	6	6	6	Node 2 with left child 4
5	Visit node	5	0	0	5	6	5	Node 5 (val=5)
6	Return to node	2	4	5	11	11	9	Node 2 with children 4 and 5
7	Return to node	1	9	0	10	11	10	Node 1 with left subtree max 9
8	Visit node	3	0	0	-3	11	-3	Node 3 (val=-3)
9	Visit node	6	0	0	6	11	6	Node 6 (val=6)
10	Return to node	3	0	6	3	11	3	Node 3 with right child 6
11	Return to node	1	9	3	14	14	12	Node 1 with left 9 and right 3
12	End	null	null	null	null	14	null	Traversal complete, max path sum = 14

💡 All nodes visited, recursion ends, global max path sum is 14

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 11	Final
maxSum	-∞	4	11	11	14	14
Return Value at Node 4	N/A	4	N/A	N/A	N/A	N/A
Return Value at Node 2	N/A	N/A	9	N/A	N/A	N/A
Return Value at Node 6	N/A	N/A	N/A	6	N/A	N/A
Return Value at Node 3	N/A	N/A	N/A	3	N/A	N/A
Return Value at Node 1	N/A	N/A	N/A	N/A	12	N/A

Key Moments - 3 Insights

Why do we use Math.max(0, maxPathSum(child)) instead of just maxPathSum(child)?

Because negative path sums reduce the total, we ignore them by taking max with 0. See execution_table rows 3 and 8 where left or right max path is 0 instead of negative.

Why do we update the global max with left + node.val + right instead of just node.val + max(left, right)?

The global max considers paths passing through the current node connecting left and right subtrees (a 'V' shape). The return value only includes one side to keep paths valid. See execution_table rows 6 and 11 where global max updates with sum of left + node + right.

What does the return value represent at each node?

It represents the maximum path sum starting at the current node and extending down to one child only, to be used by the parent node. This ensures paths are continuous and do not branch. See variable_tracker for return values.

Visual Quiz - 3 Questions

Look at the execution_table at step 6. What is the global max updated to?

A 11

B 7

C 6

D 4

💡 Hint

Check the 'Global Max Updated' column at step 6 in execution_table.

At which step does the recursion return a value of 3 for node 3?

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look at the 'Return Value' column for node 3 in execution_table rows 8-11.

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

A It would remain 11

B It would decrease to 6

C It would increase

D It would become 0

💡 Hint

Consider how negative values affect left + node + right sums in execution_table row 6.

Concept Snapshot

DP on Trees Maximum Path Sum:
- Use recursion to find max path sums from left and right children.
- Ignore negative sums by max(0, childSum).
- Update global max with left + node + right.
- Return node + max(left, right) to parent.
- Final global max is max path sum anywhere in tree.

Full Transcript

This visualization shows how to find the maximum path sum in a binary tree using dynamic programming. We start at the root and recursively calculate the maximum path sums from left and right subtrees. At each node, we compute 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 by taking max with zero. We update a global maximum if this path sum is larger than the current global max. The function returns the maximum path sum including the current node and one subtree to ensure paths are continuous. The execution table traces each step visiting nodes, calculating left and right max paths, updating the global max, and returning values. The variable tracker shows how the global max and return values change. Key moments clarify why negative sums are ignored, why the global max includes both children, and what the return value means. The quiz tests understanding of these steps and effects of changing node values. This method ensures we find the highest sum path anywhere in the tree, even if it does not pass through the root.

Practice

1. What does the "maximum path sum" in a binary tree represent?
Maximum path sum means the largest sum of node values along any path in the tree.

easy

A. The sum of node values from root to the deepest leaf

B. The sum of all node values in the tree

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

D. The largest sum of node values along any path in the tree

Solution

1. Step 1: Understand the definition of maximum path sum

   The maximum path sum is the highest sum you can get by adding node values along any path in the tree. The path can start and end at any nodes.

2. Step 2: Differentiate from other sums

   It is not just the sum of all nodes, nor the max single node, nor limited to root-to-leaf paths. It considers any path.

3. Final Answer:

   The largest sum of node values along any path in the tree -> Option D

4. Quick Check:

   Maximum path sum = largest path sum [OK]

Hint: Maximum path sum is any path's largest sum, not just root paths [OK]

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking path must start at root
• Considering only single node values

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

easy

A. int maxPathSum(TreeNode root) throws Exception

B. public int maxPathSum(TreeNode root)

C. void maxPathSum(TreeNode root)

D. public static maxPathSum(TreeNode root)

Solution

1. Step 1: Check method return type and parameters

   The method should return an int (the max sum) and accept a TreeNode parameter.

2. Step 2: Validate Java syntax

   public int maxPathSum(TreeNode root) uses correct syntax. int maxPathSum(TreeNode root) throws Exception unnecessarily throws Exception, the void version returns wrong type, the version without return type is invalid.

3. Final Answer:

   public int maxPathSum(TreeNode root) -> Option B

4. Quick Check:

   Correct method signature returns int and takes TreeNode [OK]

Hint: Method must return int and accept TreeNode parameter [OK]

Common Mistakes:

• Using void return type instead of int
• Missing return type in method signature
• Adding unnecessary throws Exception

3. Given the following Java code snippet for maximum path sum in a binary tree, what is the printed output?

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int v) { val = v; }
}

public class Solution {
  int maxSum = Integer.MIN_VALUE;

  public int maxPathSum(TreeNode root) {
    maxGain(root);
    return maxSum;
  }

  private 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);
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(-10);
    root.left = new TreeNode(9);
    root.right = new TreeNode(20);
    root.right.left = new TreeNode(15);
    root.right.right = new TreeNode(7);
    Solution sol = new Solution();
    System.out.println(sol.maxPathSum(root));
  }
}

medium

A. 42

B. 35

C. 27

D. 20

Solution

1. Step 1: Trace maxGain for each node

   Calculate maxGain for leaves: 9 returns 9, 15 returns 15, 7 returns 7. For node 20: leftGain=15, rightGain=7, priceNewPath=20+15+7=42, maxSum=42. For root -10: leftGain=9, rightGain=20+15=35 (maxGain returns node.val + max(leftGain,rightGain), so for right child maxGain=35), priceNewPath at root = -10 + 9 + 35 = 34, maxSum remains 42.

2. Step 2: Determine maxSum after full traversal

   maxSum is updated to 42 at node 20, which is the maximum path sum.

3. Final Answer:

   42 -> Option A

4. Quick Check:

   Max path sum = 42 [OK]

Hint: Max path sum includes node plus max gains from left and right [OK]

Common Mistakes:

• Ignoring negative node values
• Not resetting maxSum correctly
• Confusing return value with maxSum

4. Identify the bug in this Java method for maximum path sum and select the fix:

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

medium

A. Change return type to void

B. Remove maxSum update line

C. Add Math.max(..., 0) to leftGain and rightGain to ignore negative sums

D. Return node.val + leftGain + rightGain instead

Solution

1. Step 1: Analyze handling of negative gains

   Without Math.max(..., 0), negative leftGain or rightGain reduce path sum incorrectly.

2. Step 2: Fix by ignoring negative gains

   Use int leftGain = Math.max(maxGain(node.left), 0) and similarly for rightGain to ignore negative paths.

3. Final Answer:

   Add Math.max(..., 0) to leftGain and rightGain to ignore negative sums -> Option C

4. Quick Check:

   Ignore negative gains with Math.max(..., 0) [OK]

Hint: Ignore negative child sums by max with zero [OK]

Common Mistakes:

• Not ignoring negative sums causing wrong maxSum
• Changing return type incorrectly
• Removing maxSum update line

5. You want to find the maximum path sum in a binary tree where nodes can have negative values. Which approach correctly applies dynamic programming on trees to solve this?

Choose the best description of the approach.

hard

A. Use post-order traversal; at each node, compute max gain from left and right ignoring negatives; update global max with node value plus both gains; return node value plus max gain of one side

B. Use pre-order traversal; sum all node values; return the sum as max path sum

C. Use in-order traversal; keep track of max node value only; return max node value

D. Use level-order traversal; sum values at each level; return max level sum

Solution

1. Step 1: Understand dynamic programming on trees

   Post-order traversal ensures children are processed before parent, allowing calculation of max gains from subtrees.

2. Step 2: Apply max gain logic ignoring negative sums

   At each node, calculate max gain from left and right children ignoring negatives, update global max path sum with node plus both gains, and return node plus max gain of one side for parent's use.

3. Final Answer:

   Use post-order traversal; at each node, compute max gain from left and right ignoring negatives; update global max with node value plus both gains; return node value plus max gain of one side -> Option A

4. Quick Check:

   Post-order + max gain ignoring negatives = correct DP approach [OK]

Hint: Use post-order and ignore negative gains for max path sum [OK]

Common Mistakes:

• Using wrong traversal order
• Summing all nodes instead of max path
• Ignoring negative values in gains