DP on Trees Maximum Path Sum in DSA Go

Mental Model

We find the biggest sum of values along any path in a tree by checking each node's best path through its children and updating a global max.

Analogy: Imagine climbing a mountain with branches. At each fork, you choose the best path up and keep track of the highest peak you can reach from any path.

      1
     / \
    2   3
   / \
  4   5

Each node has a value. We want the path with the largest sum anywhere in this tree.

Dry Run Walkthrough

Input: Tree with nodes: 1(10), 2(2), 3(10), 4(20), 5(1), edges: 1-2, 1-3, 2-4, 2-5

Goal: Find the maximum sum of values on any path in the tree.

Step 1: Start DFS at node 4 (leaf), max path from 4 is 20

4(20) -> null

Why: Leaf nodes return their own value as max path

Step 2: Start DFS at node 5 (leaf), max path from 5 is 1

5(1) -> null

Why: Leaf nodes return their own value as max path

Step 3: At node 2, calculate max path from children: max(20,1) = 20, max path through 2 is max(2 + 20, 2 + 1, 2) = 22

2(2) -> 4(20), 5(1)

Why: We pick the best child path to add to node 2's value

Step 4: Check if path through node 2 combining both children is bigger: 20 + 2 + 1 = 23, update global max to 23

Path 4 -> 2 -> 5 sum = 23

Why: Path can go through node 2 connecting both children

Step 5: At node 3 (leaf), max path is 10

3(10) -> null

Why: Leaf node returns its own value

Step 6: At node 1, max path from children: max(22, 10) = 22, max path through 1 is max(10 + 22, 10 + 10, 10) = 32

1(10) -> 2(22), 3(10)

Why: Add best child path to node 1's value

Step 7: Check if path through node 1 combining both children is bigger: 22 + 10 + 10 = 42, update global max to 42

Path 4 -> 2 -> 1 -> 3 sum = 42

Why: Path can go through node 1 connecting both children

Result:

Maximum path sum is 42, path is 4 -> 2 -> 1 -> 3

Annotated Code

DSA Go

package main

import "fmt"

// TreeNode represents a node in the tree
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// maxPathSumHelper returns max path sum starting from node and updates global max
func maxPathSumHelper(node *TreeNode, maxSum *int) int {
    if node == nil {
        return 0
    }

    // max path sum from left child, ignore negative sums
    leftMax := max(0, maxPathSumHelper(node.Left, maxSum))
    // max path sum from right child, ignore negative sums
    rightMax := max(0, maxPathSumHelper(node.Right, maxSum))

    // max path sum passing through this node (including both children)
    currentSum := node.Val + leftMax + rightMax

    // update global max if currentSum is bigger
    if currentSum > *maxSum {
        *maxSum = currentSum
    }

    // return max path sum starting from this node going down one side
    return node.Val + max(leftMax, rightMax)
}

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

func maxPathSum(root *TreeNode) int {
    if root == nil {
        return 0
    }
    maxSum := root.Val
    maxPathSumHelper(root, &maxSum)
    return maxSum
}

func main() {
    // Build tree:
    //       1(10)
    //      /    \
    //   2(2)    3(10)
    //   /  \
    // 4(20) 5(1)
    n4 := &TreeNode{Val: 20}
    n5 := &TreeNode{Val: 1}
    n2 := &TreeNode{Val: 2, Left: n4, Right: n5}
    n3 := &TreeNode{Val: 10}
    n1 := &TreeNode{Val: 10, Left: n2, Right: n3}

    fmt.Println(maxPathSum(n1))
}

leftMax := max(0, maxPathSumHelper(node.Left, maxSum))

calculate max path sum from left child ignoring negative sums

rightMax := max(0, maxPathSumHelper(node.Right, maxSum))

calculate max path sum from right child ignoring negative sums

currentSum := node.Val + leftMax + rightMax

sum path through current node including both children

if currentSum > *maxSum { *maxSum = currentSum }

update global max path sum if current path is better

return node.Val + max(leftMax, rightMax)

return max path sum starting from current node going down one side

Output

42

Complexity Analysis

Time: O(n) because we visit each node once in DFS

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach checking all paths is O(n^2), this DP approach is efficient with O(n)

Edge Cases

Tree with single node

Returns the value of the single node as max path sum

DSA Go

if node == nil { return 0 }

Tree with negative values

Ignores negative child paths by taking max with 0 to avoid decreasing sum

DSA Go

leftMax := max(0, maxPathSumHelper(node.Left, maxSum))

Empty tree (root is nil)

Function returns 0 or handles nil safely

DSA Go

if node == nil { return 0 }

When to Use This Pattern

When asked for the maximum sum path in a tree that can start and end anywhere, use DP on trees with DFS to track max sums including both children and update a global max.

Common Mistakes

Mistake: Not ignoring negative sums from children, which lowers the max path sum
Fix: Use max(0, childSum) to ignore negative child paths

Mistake: Returning sum including both children instead of only one side for recursion return
Fix: Return node.Val + max(leftMax, rightMax) to keep path linear upwards

Summary

Finds the maximum sum of values on any path in a binary tree.

Use when you need the highest sum path that can start and end at any nodes in the tree.

The key is to track max sums from children ignoring negatives and update a global max including both children at each node.

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