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.