DP on Trees Maximum Path Sum in DSA Go - Build from Scratch

DP on Trees Maximum Path Sum

📖 Scenario: You are working with a tree data structure representing a network of connected nodes. Each node has a value. You want to find the maximum sum of values along any path in the tree. A path can start and end at any nodes but must follow the tree edges.

🎯 Goal: Build a Go program that constructs a tree, sets up a helper variable, implements a depth-first search with dynamic programming to find the maximum path sum, and prints the result.

📋 What You'll Learn

Create a tree node struct with an integer value and children slice

Build a sample tree with exact node values and connections

Create a variable to track the maximum path sum

Write a recursive function to compute max path sums using DP on trees

Print the maximum path sum found

💡 Why This Matters

🌍 Real World

Finding maximum path sums in trees is useful in network analysis, game development, and hierarchical data processing.

💼 Career

Understanding DP on trees and recursive algorithms is important for software engineering roles involving complex data structures and optimization problems.

1

Create the Tree Structure and Sample Tree

Define a struct called TreeNode with an int field Val and a slice of pointers to TreeNode called Children. Then create the following tree nodes with these exact values: root with value 1, node2 with value 2, node3 with value 3, node4 with value 4, and node5 with value 5. Connect the nodes so that root has children node2 and node3, node2 has child node4, and node3 has child node5.

DSA Go

// Define TreeNode struct and create tree nodes with connections
// Your code here

Hint

Use a struct with a value and a slice of pointers for children. Create nodes with &TreeNode{Val: value} and connect children slices.

2

Add a Variable to Track Maximum Path Sum

Inside the main function, create a variable called maxSum of type int and initialize it to the smallest possible integer value -1 << 31.

DSA Go

package main

type TreeNode struct {
    Val      int
    Children []*TreeNode
}

func main() {
    root := &TreeNode{Val: 1}
    node2 := &TreeNode{Val: 2}
    node3 := &TreeNode{Val: 3}
    node4 := &TreeNode{Val: 4}
    node5 := &TreeNode{Val: 5}

    root.Children = []*TreeNode{node2, node3}
    node2.Children = []*TreeNode{node4}
    node3.Children = []*TreeNode{node5}

    // Create variable maxSum initialized to -1 << 31
    // Your code here
}

Hint

Use maxSum := -1 << 31 to set the smallest integer value in Go.

3

Write Recursive Function to Compute Maximum Path Sum

Write a recursive function called dfs that takes a pointer to TreeNode and returns an int. Inside dfs, compute the maximum path sum starting from the current node and update the maxSum variable if a larger sum is found. Use the following logic: for each child, recursively call dfs and keep track of the top two maximum child sums. The function should return the maximum sum of the current node's value plus the maximum child sum or zero if negative. Update maxSum with the sum of the current node's value plus the top two child sums if it is greater than the current maxSum. Call dfs on root inside main.

DSA Go

package main

type TreeNode struct {
    Val      int
    Children []*TreeNode
}

func main() {
    root := &TreeNode{Val: 1}
    node2 := &TreeNode{Val: 2}
    node3 := &TreeNode{Val: 3}
    node4 := &TreeNode{Val: 4}
    node5 := &TreeNode{Val: 5}

    root.Children = []*TreeNode{node2, node3}
    node2.Children = []*TreeNode{node4}
    node3.Children = []*TreeNode{node5}

    maxSum := -1 << 31

    // Write dfs function and call dfs(root)
    // Your code here
}

Hint

Use recursion to explore children. Track top two max child sums. Update maxSum with node.Val + max1 + max2. Return node.Val + max1 or 0 if negative.

4

Print the Maximum Path Sum

Add a fmt.Println statement inside main to print the value of maxSum after calling dfs(root). Import the fmt package at the top.

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val      int
    Children []*TreeNode
}

func main() {
    root := &TreeNode{Val: 1}
    node2 := &TreeNode{Val: 2}
    node3 := &TreeNode{Val: 3}
    node4 := &TreeNode{Val: 4}
    node5 := &TreeNode{Val: 5}

    root.Children = []*TreeNode{node2, node3}
    node2.Children = []*TreeNode{node4}
    node3.Children = []*TreeNode{node5}

    maxSum := -1  max1 {
                max2 = max1
                max1 = val
            } else if val > max2 {
                max2 = val
            }
        }
        currentSum := node.Val + max1 + max2
        if currentSum > maxSum {
            maxSum = currentSum
        }
        ret := node.Val + max1
        if ret < 0 {
            return 0
        }
        return ret
    }

    dfs(root)

    // Print maxSum
    // Your code here
}

Hint

Use fmt.Println(maxSum) to print the maximum path sum after DFS completes.

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