Maximum Path Sum in Binary Tree in DSA Typescript - 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 through current node

↓

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

Start from root, recursively find max path sums from left and right children, update global max with path through current node, return max path including one child 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, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
}

Recursively computes max path sum in binary tree, updating global max sum at each node.

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 + 0 + 0 = 1	1	1 + max(0,0) = 1	1
2	Visit node	2	0	0	2 + 0 + 0 = 2	2	2 + max(0,0) = 2	1 -> 2
3	Back to node	1	2	0	1 + 2 + 0 = 3	3	1 + max(2,0) = 3	1 -> 2
4	Visit node	3	0	0	-3 + 0 + 0 = -3	3	-3 + max(0,0) = 0	1 -> 2, 3
5	Back to node	1	2	0	1 + 2 + 0 = 3	3	3	1 -> 2, 3
6	Final	root	-	-	-	3	-	Final max path sum = 3

💡 All nodes visited, global max updated to 3

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
maxSum	-Infinity	1	2	3	3	3	3
left	-	0	0	2	0	2	-
right	-	0	0	0	0	0	-
return value	-	1	2	3	0	3	-

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 node.val + left + right instead of just one side?

Because the max path can pass through the current node connecting left and right subtrees. This is shown in execution_table row 3 where current path sum includes both left and right.

Why does the dfs function return node.val + max(left, right) and not include both sides?

Because when returning to parent, path must be linear (one branch). Including both sides would create a fork, which is not allowed in path definition. See return values in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the global max value?

A 1

B 3

C 4

D 2

💡 Hint

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

At which step does the algorithm ignore a negative path sum by using 0 instead?

A Step 4

B Step 2

C Step 1

D Step 5

💡 Hint

Look at 'Left Max' and 'Right Max' columns for negative values replaced by 0 in execution_table

If the node value at step 4 was positive instead of -3, how would the global max change?

A It would stay the same

B It would decrease

C It would increase

D It would become zero

💡 Hint

Consider how global max updates with current path sum in execution_table rows

Concept Snapshot

Maximum Path Sum in Binary Tree:
- Use DFS to explore each node
- Calculate max path sum from left and right children, ignore negatives
- 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. We start at the root and recursively calculate the maximum path sums from the left and right children. Negative sums are ignored by taking the maximum with zero. At each node, we calculate the path sum that passes through it by adding its value and the maximum sums from both children. We update a global maximum if this sum is higher than before. When returning to the parent, we only include the node's value plus the larger of the two child sums to keep the path linear. The final global maximum after visiting all nodes is the maximum path sum in the tree.