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

Concept Flow - DP on Trees Maximum Path Sum

Start at root node

↓

Recursively compute max path sum from left subtree

↓

Recursively compute max path sum from right subtree

↓

Calculate max path through current node: max(left,0) + node.val + max(right,0)

↓

Update global max if current path sum is higher

↓

Return max path sum including current node and one subtree

↓

Repeat for all nodes

↓

Final global max is the answer

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

Execution Sample

DSA Typescript

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

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 Path Sum	Global Max	Return Value	Visual State
1	Visit node	1	0	0	1	1	1	Node1(1)
2	Visit node	2	0	0	2	2	2	Node2(2)
3	Back to node	1	2	0	3	3	3	Node1(1) with left=2
4	Visit node	3	0	0	-3	3	0	Node3(-3)
5	Back to node	1	2	0	3	3	3	Node1(1) with left=2, right=0
6	Visit node	4	0	0	4	4	4	Node4(4)
7	Visit node	5	0	0	5	5	5	Node5(5)
8	Back to node	4	0	5	9	9	9	Node4(4) with right=5
9	Back to node	1	2	9	12	12	12	Node1(1) with left=2, right=9
10	End	null	-	-	-	12	-	Final max path sum = 12

💡 All nodes visited, recursion ends with global max path sum 12

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	After Step 8	After Step 9	Final
maxSum	-Infinity	1	2	3	3	3	4	5	9	12	12
left	-	0	0	2	0	2	0	0	0	2	-
right	-	0	0	0	0	0	0	5	5	9	-

Key Moments - 3 Insights

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

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

Why do we update global max with left + node.val + right instead of just returning that?

The global max tracks the best path anywhere in the tree, which can include both left and right children plus current node. But the return value must be a path continuing upwards, so it only includes one side plus node. See rows 3, 8, and 9.

What happens if the tree has all negative values?

Since we take max with 0 for children, the path sum at a node can be just the node's value. The global max will be the largest single node value. This is why maxSum starts at -Infinity and updates accordingly.

Visual Quiz - 3 Questions

Look at the execution_table at Step 9, what is the global max path sum?

A 5

B 9

C 12

D 3

💡 Hint

Check the 'Global Max' column at Step 9 in execution_table

At which step does the right max first become 5?

A Step 6

B Step 8

C Step 7

D Step 9

💡 Hint

Look at the 'Right Max' column in execution_table rows 6,7,8

If we remove Math.max(..., 0) and allow negative sums, what would happen to the global max?

A It could decrease due to negative paths

B It would stay the same

C It would always increase

D It would become zero

💡 Hint

Refer to key_moments about ignoring negative sums and their effect on global max

Concept Snapshot

DP on Trees Maximum Path Sum:
- Use DFS to get max path sums from left and right children
- Ignore negative sums by max(childSum, 0)
- Update global max with left + node.val + right
- Return node.val + 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 compute the maximum path sums from left and right subtrees. At each node, we calculate 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 higher than before. The function returns the maximum path sum including the current node and one subtree to its parent. The process repeats for all nodes, and the global maximum at the end is the answer. Key points include ignoring negative sums to avoid reducing the total and understanding why the global max includes both children but the return value only includes one side. The execution table traces each step with node visits, computed values, and updates to the global max. The variable tracker shows how maxSum, left, and right values change over time. 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 tree represent in the context of dynamic programming on trees?

easy

A. The sum of all node values in the tree

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

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

D. The longest path length in the tree

Solution

1. Step 1: Understand the problem definition

   The maximum path sum is about finding the path between any two nodes that yields the highest sum of node values.

2. Step 2: Differentiate from other sums

   It is not the sum of all nodes or just the max node value, but the max sum along a connected path.

3. Final Answer:

   The largest sum of node values along any path between two nodes in the tree -> Option B

4. Quick Check:

   Maximum path sum = max sum on any path [OK]

Hint: Maximum path sum is about any path, not whole tree sum [OK]

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking it is just the max node value
• Assuming path must start at root

2. Which of the following TypeScript function signatures correctly represents a recursive function to find maximum path sum in a binary tree node?

easy

A. function maxPathSum(node: TreeNode): void

B. function maxPathSum(node: number): number

C. function maxPathSum(): number

D. function maxPathSum(node: TreeNode | null): number

Solution

1. Step 1: Check parameter type

   The function must accept a TreeNode or null to handle empty nodes.

2. Step 2: Check return type

   It should return a number representing the max path sum from that node.

3. Final Answer:

   function maxPathSum(node: TreeNode | null): number -> Option D

4. Quick Check:

   Correct parameter and return type [OK]

Hint: Function must accept node or null and return number [OK]

Common Mistakes:

• Using wrong parameter type (e.g., number instead of TreeNode)
• Returning void instead of number
• Not allowing null for leaf children

3. Consider the following TypeScript code snippet for maximum path sum in a binary tree:

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

function maxPathSum(root: TreeNode | null): number {
  let maxSum = -Infinity;
  function dfs(node: TreeNode | null): number {
    if (!node) return 0;
    const left = Math.max(dfs(node.left), 0);
    const 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));

What is the output of this code?

medium

A. 3

B. 5

C. 6

D. 1

Solution

1. Step 1: Trace DFS on tree nodes

   For node 2 and 3, max path sums are 2 and 3 respectively. For root 1, left=2, right=3.

2. Step 2: Calculate maxSum updates

   maxSum updates to max(-Infinity, 1+2+3) = 6. Return value for root is 1 + max(2,3) = 4 but maxSum remains 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Sum of path 2->1->3 = 6 [OK]

Hint: Sum left + node + right for max path sum [OK]

Common Mistakes:

• Returning max path from root only, ignoring subtrees
• Not using Math.max with 0 to ignore negative sums
• Confusing return value with maxSum global

4. The following TypeScript code attempts to find the maximum path sum in a binary tree but has a bug:

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

What is the bug in this code?

medium

A. It does not ignore negative sums from left or right subtree

B. It returns void instead of number

C. It does not handle null root

D. It uses global variable incorrectly

Solution

1. Step 1: Analyze subtree sums usage

   The code uses left and right sums directly without ignoring negative values.

2. Step 2: Identify impact on maxSum

   Negative sums can reduce maxSum, so we must use Math.max(dfs(...), 0) to ignore negatives.

3. Final Answer:

   It does not ignore negative sums from left or right subtree -> Option A

4. Quick Check:

   Negative subtree sums must be ignored [OK]

Hint: Use Math.max(dfs(...), 0) to ignore negatives [OK]

Common Mistakes:

• Not checking for negative subtree sums
• Assuming dfs returns void
• Ignoring null root case

5. Given a binary tree where some nodes have negative values, how would you modify the dynamic programming approach to find the maximum path sum that can start and end at any node, but the path must go downwards (only from parent to child)?

hard

A. Use DFS to compute max downward path sum at each node ignoring negative sums by max(0, childSum)

B. Use BFS to find the longest path ignoring node values

C. Sum all node values and subtract minimum node value

D. Only consider paths that include the root node

Solution

1. Step 1: Understand downward path constraint

   The path must go downwards from parent to child, so use DFS to explore children.

2. Step 2: Handle negative values

   Ignore negative sums by taking max(0, childSum) to avoid reducing path sum.

3. Step 3: Calculate max path sum

   At each node, max downward path sum = node.val + max(leftChildSum, rightChildSum, 0).

4. Final Answer:

   Use DFS to compute max downward path sum at each node ignoring negative sums by max(0, childSum) -> Option A

5. Quick Check:

   Downward path + ignore negatives = DFS with max(0, childSum) [OK]

Hint: Downward path max sum uses DFS and max(0, childSum) [OK]

Common Mistakes:

• Using BFS instead of DFS
• Ignoring negative values incorrectly
• Forcing path through root only