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

Concept Flow - DP on Trees Maximum Path Sum

Start at root node

↓

Recursively find max path sum from left child

↓

Recursively find max path sum from right child

↓

Calculate max path through current node

↓

Update global max if current path is higher

↓

Return max path sum including current node and one child

↓

Repeat for all nodes

↓

Final global max is answer

We start at the root and recursively find max path sums from left and right children. At each node, we calculate max path through it and update global max. We return max path including current node and one child to parent.

Execution Sample

DSA Javascript

let maxSum = -Infinity;
function maxPathSum(node) {
  if (!node) return 0;
  let left = Math.max(0, maxPathSum(node.left));
  let right = Math.max(0, maxPathSum(node.right));
  maxSum = Math.max(maxSum, node.val + left + 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 children and updating a global max.

Execution Table

Step	Operation	Node Visited	Left Max	Right Max	Current Max Path	Global Max	Return Value	Visual State
1	Visit node	1	N/A	N/A	N/A	-∞	N/A	1
2	Visit node	2	N/A	N/A	N/A	-∞	N/A	2
3	Visit node	4	0	0	4	4	4	4
4	Return from node 4	4	0	0	4	4	4	4
5	Visit node	5	0	0	5	5	5	5
6	Return from node 5	5	0	0	5	5	5	5
7	Calculate at node 2	2	4	5	11	11	7	2 -> 4,5
8	Return from node 2	2	4	5	11	11	7	2 -> 4,5
9	Visit node	3	N/A	N/A	N/A	11	N/A	3
10	Visit node	6	0	0	6	11	6	6
11	Return from node 6	6	0	0	6	11	6	6
12	Visit node	7	0	0	7	11	7	7
13	Return from node 7	7	0	0	7	11	7	7
14	Calculate at node 3	3	6	7	16	16	10	3 -> 6,7
15	Return from node 3	3	6	7	16	16	10	3 -> 6,7
16	Calculate at node 1	1	7	10	18	18	11	1 -> 2,3
17	Return from node 1	1	7	10	18	18	11	1 -> 2,3
18	End	N/A	N/A	N/A	N/A	18	N/A	Final max path sum = 18

💡 All nodes visited, global max updated to 18 which is the maximum path sum

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 7	After Step 11	After Step 13	After Step 14	After Step 16	Final
maxSum	-∞	4	5	11	11	11	16	18	18
left	N/A	0	0	4	0	0	6	7	7
right	N/A	0	0	5	0	0	7	10	10
returnVal	N/A	4	5	7	6	7	10	11	11

Key Moments - 3 Insights

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

Because negative path sums would reduce the total, we ignore them by taking max with 0. See execution_table rows 3 and 5 where left and right max are 0 if child returns negative or no node.

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

Because the max path can pass through the current node connecting both left and right children. This is shown in execution_table rows 7, 14, and 16 where current max path includes both sides.

What does the return value represent at each node?

It represents the maximum path sum including the current node and only one child path (left or right) to continue upwards. This is why in execution_table rows 7, 14, and 16 return values are node.val + max(left, right).

Visual Quiz - 3 Questions

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

A 7

B 11

C 5

D 4

💡 Hint

Check the 'Global Max' column at step 7 in execution_table

At which step does the global max first become 16?

A Step 14

B Step 13

C Step 16

D Step 10

💡 Hint

Look at the 'Global Max' column in execution_table rows around step 14

If node 5 had a negative value, how would the return value at node 2 change at step 7?

A It would stay the same because negative values are ignored

B It would increase because negative values add up

C It would decrease because left max remains 4 but right max becomes 0

D It would become negative

💡 Hint

Recall that negative child sums are replaced by 0, so right max would be 0 if node 5 is negative

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 with 0
- Update global max with node.val + left + right
- Return node.val + max(left, right) to parent
- Final global max is the answer

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 visit each node. For each node, we calculate the maximum path sum from its left and right children, ignoring negative sums by taking the maximum with zero. We then calculate the maximum path sum passing through the current node by adding its value and the left and right max sums. We update a global maximum if this path sum is higher than the current global max. The function returns the maximum path sum including the current node and one child path to its parent. The execution table traces each step visiting nodes, calculating left and right max sums, updating the global max, and returning values. The variable tracker shows how maxSum 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 visual quiz tests understanding of these steps. The final maximum path sum found is 18.

Practice

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

easy

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

B. The number of nodes in the longest path

C. The smallest sum of node values along any path

D. The sum of all node values in the tree

Solution

1. Step 1: Understand the path definition

   A path in a tree is any sequence of nodes connected by edges, not necessarily starting at the root.

2. Step 2: Define maximum path sum meaning

   The maximum path sum is the highest total value you get by adding node values along any such path.

3. Final Answer:

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

4. Quick Check:

   Maximum path sum = largest node value sum [OK]

Hint: Maximum path sum is about node values, not count or minimum [OK]

Common Mistakes:

• Confusing path length with sum
• Thinking path must start at root
• Choosing sum of all nodes instead of max path

2. Which of the following is the correct base case for a recursive function computing maximum path sum in a binary tree node?

function maxPathSum(node) {
  if (___) return 0;
  // rest of code
}

easy

A. node.value === 0

B. node.left === null && node.right === null

C. node === null

D. node === undefined

Solution

1. Step 1: Identify when recursion should stop

   When the node is empty (null), there is no path, so return 0.

2. Step 2: Check options for base case

   Only checking if node is null correctly handles leaf children and empty trees.

3. Final Answer:

   node === null -> Option C

4. Quick Check:

   Base case: node null means no path [OK]

Hint: Base case is node === null to stop recursion [OK]

Common Mistakes:

• Using node.value === 0 which is incorrect
• Checking both children null instead of node null
• Using node === undefined which is less common

3. What is the output of the following code snippet?

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function maxPathSum(root) {
  let maxSum = -Infinity;
  function dfs(node) {
    if (node === null) return 0;
    let left = Math.max(dfs(node.left), 0);
    let right = Math.max(dfs(node.right), 0);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
}

const tree = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(maxPathSum(tree));

medium

A. 6

B. 5

C. 3

D. 1

Solution

1. Step 1: Calculate max path sums for each node

   For leaf nodes 2 and 3, max path sum is their value (2 and 3). For root 1, left=2, right=3, sum=1+2+3=6.

2. Step 2: Update maxSum and return correct values

   maxSum updates to 6 at root. Return values propagate correctly.

3. Final Answer:

   6 -> Option A

4. Quick Check:

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

Hint: Add node + max left + max right, ignore negatives [OK]

Common Mistakes:

• Forgetting to ignore negative sums
• Returning node.val + left + right instead of max(left, right)
• Confusing maxSum update with return value

4. Find the bug in this code for maximum path sum in a binary tree:

function maxPathSum(root) {
  let maxSum = -Infinity;
  function dfs(node) {
    if (!node) return 0;
    let left = dfs(node.left);
    let right = dfs(node.right);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
}

medium

A. It returns maxSum before dfs call

B. It does not ignore negative sums from children

C. It uses wrong base case condition

D. It adds node.val twice in maxSum

Solution

1. Step 1: Check handling of negative child sums

   The code uses left = dfs(node.left) directly without ignoring negatives, which can reduce maxSum incorrectly.

2. Step 2: Correct approach to ignore negatives

   Should use left = Math.max(dfs(node.left), 0) and similarly for right to avoid negative paths.

3. Final Answer:

   It does not ignore negative sums from children -> Option B

4. Quick Check:

   Ignore negatives to maximize path sum [OK]

Hint: Use Math.max(childSum, 0) to skip negative paths [OK]

Common Mistakes:

• Not ignoring negative sums
• Returning before dfs call
• Wrong base case check

5. Given a binary tree where nodes can have negative values, how would you modify the maximum path sum algorithm to handle the case where all node values are negative?
Choose the best approach:

hard

A. Initialize maxSum to 0 and ignore negative sums

B. Only consider paths starting at the root

C. Return 0 if all nodes are negative

D. Initialize maxSum to -Infinity and allow paths with negative sums

Solution

1. Step 1: Understand negative values impact

   If all nodes are negative, ignoring negative sums by replacing with 0 would incorrectly return 0 instead of the max negative value.

2. Step 2: Use -Infinity initialization and allow negative sums

   Initialize maxSum to -Infinity and do not ignore negative sums completely, so the max negative node is chosen.

3. Final Answer:

   Initialize maxSum to -Infinity and allow paths with negative sums -> Option D

4. Quick Check:

   Allow negative sums to handle all-negative nodes [OK]

Hint: Use -Infinity start and allow negatives for all-negative trees [OK]

Common Mistakes:

• Ignoring negatives leads to wrong zero result
• Returning 0 when no positive path exists
• Restricting paths to root only