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

↓

Update global max if current path sum is greater

↓

Return max path sum for one side + current node to parent

↓

Repeat for all nodes

↓

Final global max is the answer

We visit each node, find max path sums from left and right children, update global max with paths passing through the node, and return max single-side path sum to parent.

Execution Sample

DSA Go

func maxPathSum(root *TreeNode) int {
  maxSum := math.MinInt32
  var dfs func(*TreeNode) int
  dfs = func(node *TreeNode) int {
    if node == nil { return 0 }
    left := max(dfs(node.Left), 0)
    right := max(dfs(node.Right), 0)
    maxSum = max(maxSum, node.Val + left + right)
    return node.Val + 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 (10)	?	?	?	-∞	?	10
2	Visit	Node 2 (2)	?	?	?	-∞	?	2
3	Visit	Node 4 (20)	0	0	20	-∞	20	20
4	Return	Node 4	0	0	20	20	20	20
5	Visit	Node 5 (1)	0	0	1	20	1	20 -> 1
6	Return	Node 5	0	0	1	20	1	20 -> 1
7	Calculate	Node 2	20	1	23	23	22	10 -> 2 -> 20, 1
8	Return	Node 2	20	1	23	23	22	10 -> 2 -> 20, 1
9	Visit	Node 3 (-25)	?	?	?	23	?	10 -> 2 -> 20, 1
10	Visit	Node 6 (3)	0	0	3	23	3	10 -> 2 -> 20, 1
11	Return	Node 6	0	0	3	23	3	10 -> 2 -> 20, 1
12	Visit	Node 7 (4)	0	0	4	23	4	10 -> 2 -> 20, 1
13	Return	Node 7	0	0	4	23	4	10 -> 2 -> 20, 1
14	Calculate	Node 3	3	4	-18	23	-21	10 -> 2 -> 20, 1
15	Return	Node 3	3	4	-18	23	-21	10 -> 2 -> 20, 1
16	Calculate	Node 1	22	0	32	32	32	10 -> 2 -> 20, 1, -25 -> 3, 4
17	Return	Node 1	22	0	32	32	32	10 -> 2 -> 20, 1, -25 -> 3, 4
18	End	-	-	-	-	32	-	Final max path sum is 32

💡 All nodes visited, global max updated to 32, recursion ends.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 7	After Step 11	After Step 13	After Step 15	After Step 17	Final
maxSum	-∞	20	20	23	23	23	23	32	32
Return Value at Node 4	N/A	20	20	20	20	20	20	20	20
Return Value at Node 5	N/A	N/A	1	1	1	1	1	1	1
Return Value at Node 2	N/A	N/A	N/A	22	22	22	22	22	22
Return Value at Node 6	N/A	N/A	N/A	N/A	3	3	3	3	3
Return Value at Node 7	N/A	N/A	N/A	N/A	N/A	4	4	4	4
Return Value at Node 3	N/A	N/A	N/A	N/A	N/A	N/A	-21	-21	-21
Return Value at Node 1	N/A	N/A	N/A	N/A	N/A	N/A	N/A	32	32

Key Moments - 3 Insights

Why do we take max(dfs(child), 0) instead of just dfs(child)?

Because negative path sums reduce the total, we ignore them by taking max with 0. See steps 3 and 5 where left and right max are 0 if 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 step 7 and step 16 where global max updates consider both sides.

What does the return value represent at each node?

It represents the max path sum for one side plus the current node, to be used by the parent. This is why in step 7 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 23

B 20

C 22

D 32

💡 Hint

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

At which step does the recursion return the value 22 for Node 2?

A Step 4

B Step 7

C Step 6

D Step 17

💡 Hint

Look at the 'Return Value' column for Node 2 in execution_table.

If we did not ignore negative sums (did not use max with 0), what would happen to the global max at Node 3 (step 14)?

A It would increase

B It would stay the same

C It would decrease

D It would become zero

💡 Hint

Check how left and right max are 3 and 4, but node.Val is -25, so negative sums affect the total.

Concept Snapshot

Maximum Path Sum in Binary Tree:
- Visit each node recursively
- Calculate max path sum from left and right children (ignore negatives)
- Update global max with node.Val + left + right
- Return max single-side path sum 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 visit each node. For each node, we calculate the maximum path sums from its left and right children, ignoring negative sums by taking max with zero. We then calculate the 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 greater. The function returns the maximum path sum for one side plus the current node to its parent. This process repeats for all nodes, and the final global maximum is the maximum path sum in the tree.