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

Concept Flow - DP on Trees Maximum Path Sum

Start at root node

↓

Compute max path sum from left subtree

↓

Compute max path sum from right subtree

↓

Calculate max path through current node

↓

Update global max if current path is higher

↓

Return max path sum including current node to parent

↓

Repeat for all nodes

↓

Final max path sum is global max

Start from root, recursively find max path sums from left and right children, update global max with paths through current node, return max path sum to parent, repeat for all nodes.

Execution Sample

DSA Go

func maxPathSum(root *TreeNode) int {
  maxSum := -1000000000
  max := func(a, b int) int {
    if a > b {
      return a
    }
    return b
  }
  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 computing 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	3	0	0	3	3	3	3
2	Visit node	2	0	0	2	3	2	3 -> 2
3	Visit node	1	0	0	1	3	1	3 -> 2 -> 1
4	Back to node	2	1	0	3	3	3	3 -> 2 -> 1
5	Back to node	3	3	0	6	6	6	3 -> 2 -> 1
6	Visit node	4	0	0	4	6	4	3 -> 2 -> 1, 4
7	Back to node	3	3	4	10	10	7	3 -> 2 -> 1, 4
8	End	root	-	-	-	10	-	Final max path sum = 10

💡 All nodes visited, recursion ends, global max path sum is 10

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	Final
maxSum	-∞	3	3	3	3	6	6	10	10
left	-	0	0	0	1	3	0	3	-
right	-	0	0	0	0	0	0	4	-
returnValue	-	3	2	1	3	6	4	7	-

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 execution_table rows 1-3 where left and right max are 0 when child returns negative or zero.

Why do we update 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 left and right subtrees. This is shown in step 7 where global max updates to 10 including both sides.

What does the return value represent at each node?

It represents the max path sum from current node down to one child, used by parent to build paths. See variable_tracker returnValue changes after each step.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the global max?

A 11

B 3

C 6

D 7

💡 Hint

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

At which step does the global max first update to a value greater than 3?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Global Max' column in execution_table and find when it changes from 3

If we did not use max(dfs(child), 0), how would the 'Left Max' and 'Right Max' columns change?

A They could be negative values

B They would be larger than current values

C They would always be zero

D They would not change

💡 Hint

Refer to key_moments about ignoring negative sums and execution_table left/right max values

Concept Snapshot

DP on Trees Maximum Path Sum:
- Use DFS to compute max path sums from children
- Ignore negative sums by max(childSum, 0)
- Update global max with node.Val + left + right
- Return node.Val + max(left, right) to parent
- Final answer is global max after full traversal

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 the left and right children. Negative sums are ignored by taking the maximum with zero. At each node, we calculate the maximum path sum passing through it by adding its value and the maximum sums from left and right. We update a global maximum if this sum is higher. The function returns the maximum sum path that can be extended to the parent node. The process repeats for all nodes, and the global maximum at the end is the answer. The execution table tracks each step, showing node visits, computed sums, and updates to the global maximum. Key moments clarify why negative sums are ignored and why the global max includes both children. The quiz tests understanding of these steps and values.

Practice

1. What does the "Maximum Path Sum" in a tree represent in the context of dynamic programming on trees?

easy

A. The largest sum of node values on any path between two nodes in the tree

B. The number of nodes in the longest path of the tree

C. The sum of all node values in the tree

D. The maximum value of a single node 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 gives the highest sum of node values.

2. Step 2: Differentiate from other sums

   It is not just the sum of all nodes or the longest path length, but the maximum sum along any path.

3. Final Answer:

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

4. Quick Check:

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

Hint: Maximum path sum means highest sum between any two nodes [OK]

Common Mistakes:

• Confusing maximum path sum with longest path length
• Thinking it is sum of all nodes
• Considering only single node values

2. Which of the following Go function signatures is correct for a recursive function that returns the maximum path sum starting from a given tree node?

easy

A. func maxPathSum(node int) int

B. func maxPathSum(node TreeNode) string

C. func maxPathSum(node *TreeNode) (int, error)

D. func maxPathSum(node *TreeNode) int

Solution

1. Step 1: Identify correct parameter type

   The function should accept a pointer to TreeNode to handle nil nodes and avoid copying.

2. Step 2: Identify correct return type

   The function returns an integer representing the maximum path sum, so return type int is correct.

3. Final Answer:

   func maxPathSum(node *TreeNode) int -> Option D

4. Quick Check:

   Pointer input and int output for max sum [OK]

Hint: Use pointer receiver and int return for max path sum [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Returning string or error instead of int
• Using wrong parameter type like int

3. Given the following Go code snippet for a binary tree node and a function to compute maximum path sum, what is the output printed?

package main

import "fmt"

type TreeNode struct {
    Val int
    Left, Right *TreeNode
}

func maxPathSumUtil(node *TreeNode, maxSum *int) int {
    if node == nil {
        return 0
    }
    left := max(0, maxPathSumUtil(node.Left, maxSum))
    right := max(0, maxPathSumUtil(node.Right, maxSum))
    *maxSum = max(*maxSum, left + right + node.Val)
    return max(left, right) + node.Val
}

func maxPathSum(root *TreeNode) int {
    maxSum := -1000000
    maxPathSumUtil(root, &maxSum)
    return maxSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    root := &TreeNode{Val: -10}
    root.Left = &TreeNode{Val: 9}
    root.Right = &TreeNode{Val: 20}
    root.Right.Left = &TreeNode{Val: 15}
    root.Right.Right = &TreeNode{Val: 7}
    fmt.Println(maxPathSum(root))
}

medium

A. 27

B. 35

C. 42

D. 20

Solution

1. Step 1: Calculate max path sums for subtrees

   Left subtree: 9 (updates maxSum to 9). Right subtree: 15 (maxSum=15), 7 (no change), at 20: left=15, right=7, *maxSum = max(15, 15+7+20)=42, returns max(15,7)+20=35.

2. Step 2: Compare and update maxSum

   At root (-10): left=max(0,9)=9, right=max(0,35)=35, *maxSum = max(42, 9+35+(-10))=max(42,34)=42.

3. Final Answer:

   42 -> Option C

4. Quick Check:

   Max path sum = 42 [OK]

Hint: Add max(0, child sums) and update global max [OK]

Common Mistakes:

• Not ignoring negative sums by using max(0, ...)
• Adding node values incorrectly
• Confusing max path sum with max root-to-leaf sum

4. The following Go function is intended to compute the maximum path sum in a binary tree. What is the bug causing incorrect results?

func maxPathSumUtil(node *TreeNode, maxSum *int) int {
    if node == nil {
        return 0
    }
    left := maxPathSumUtil(node.Left, maxSum)
    right := maxPathSumUtil(node.Right, maxSum)
    *maxSum = max(*maxSum, left + right + node.Val)
    return max(left, right) + node.Val
}

medium

A. It does not ignore negative sums from children before adding

B. It returns the sum of both children instead of max child sum

C. It does not update maxSum correctly

D. It does not handle nil nodes

Solution

1. Step 1: Check handling of negative child sums

   The function uses left and right sums directly without ignoring negative values, which can reduce the path sum.

2. Step 2: Identify fix by ignoring negatives

   To fix, use max(0, left) and max(0, right) to ignore negative sums before adding to node.Val.

3. Final Answer:

   It does not ignore negative sums from children before adding -> Option A

4. Quick Check:

   Ignore negative child sums for correct max path [OK]

Hint: Always ignore negative child sums with max(0, child) [OK]

Common Mistakes:

• Not using max(0, child) to ignore negatives
• Returning sum of both children instead of max child
• Not updating maxSum properly

5. You are given a binary tree where some nodes have negative values. How would you modify the standard DP on trees maximum path sum algorithm to correctly handle this case and find the maximum path sum?

hard

A. Ignore all negative nodes completely from the tree

B. Use max(0, child sums) to ignore negative paths and update global max with left + right + node.Val

C. Only consider paths from root to leaf nodes

D. Sum all node values regardless of sign and return the total

Solution

1. Step 1: Handle negative child sums carefully

   Use max(0, child sums) to ignore negative paths that reduce the total sum.

2. Step 2: Update global maximum path sum correctly

   Update the global max with the sum of left + right + current node value to consider paths passing through the node.

3. Final Answer:

   Use max(0, child sums) to ignore negative paths and update global max with left + right + node.Val -> Option B

4. Quick Check:

   Ignore negatives, update max with left+right+node [OK]

Hint: Ignore negative child sums, update max with combined path [OK]

Common Mistakes:

• Summing all nodes including negatives blindly
• Considering only root-to-leaf paths
• Removing negative nodes instead of ignoring sums