Maximum Path Sum in Binary Tree in DSA Go

Mental Model

Find the highest sum of values along any path in a tree, where the path can start and end at any node.

Analogy: Imagine a mountain range where each peak has a height. You want to find the highest possible trail that can go up and down connecting any peaks, not necessarily starting at the base or ending at the top.

      1
     / \
    2   3
   / \   \
  4  -5   6

Dry Run Walkthrough

Input: Binary tree: 1 -> 2 -> 4, 2 -> -5, 1 -> 3 -> 6

Goal: Find the maximum sum path anywhere in the tree

Step 1: Start at leaf node 4, max path sum from 4 is 4

4 (leaf) -> max path sum = 4

Why: Leaf nodes have max path sum equal to their own value

Step 2: At node -5, max path sum is -5

-5 (leaf) -> max path sum = -5

Why: Negative leaf node max path sum is its own value

Step 3: At node 2, calculate max path sum including children: max(4, 0) + 2 + max(-5, 0) = 6

2 -> left child 4, right child -5 -> max path sum through 2 = 6

Why: Ignore negative child sums, add positive child sums to node value

Step 4: At node 6, max path sum is 6

6 (leaf) -> max path sum = 6

Why: Leaf node max path sum is its own value

Step 5: At node 3, max path sum including child: 3 + max(6, 0) = 9

3 -> right child 6 -> max path sum through 3 = 9

Why: Add positive child max path sum to node value

Step 6: At root 1, max path sum including both children: 1 + max(2's max path sum, 0) + max(3's max path sum, 0) = 1 + 6 + 9 = 16

1 -> left child 2 (6), right child 3 (9) -> max path sum through 1 = 16

Why: Combine left and right max sums plus root for max path crossing root

Step 7: Compare all max path sums found: 4, -5, 6, 9, 16 -> maximum is 16

Maximum path sum in tree = 16

Why: Final answer is the highest sum found anywhere in the tree

Result:

Maximum path sum = 16

Annotated Code

DSA Go

package main

import (
	"fmt"
	"math"
)

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

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

func maxPathSum(root *TreeNode) int {
	maxSum := math.MinInt64

	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}

		left := max(dfs(node.Left), 0) // ignore negative sums
		right := max(dfs(node.Right), 0)

		currentSum := node.Val + left + right
		if currentSum > maxSum {
			maxSum = currentSum // update max if current path is better
		}

		return node.Val + max(left, right) // return max path sum including one child
	}

	dfs(root)
	return maxSum
}

func main() {
	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 2}
	root.Right = &TreeNode{Val: 3}
	root.Left.Left = &TreeNode{Val: 4}
	root.Left.Right = &TreeNode{Val: -5}
	root.Right.Right = &TreeNode{Val: 6}

	result := maxPathSum(root)
	fmt.Println(result)
}

left := max(dfs(node.Left), 0) // ignore negative sums

calculate max path sum from left child, ignore negative sums to avoid reducing total

right := max(dfs(node.Right), 0)

calculate max path sum from right child, ignore negative sums

currentSum := node.Val + left + right

sum path through current node including both children

if currentSum > maxSum { maxSum = currentSum // update max if current path is better }

update global max path sum if current path is larger

return node.Val + max(left, right) // return max path sum including one child

return max sum path continuing upwards through one child

Output

16

Complexity Analysis

Time: O(n) because we visit each node once in the depth-first search

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

vs Alternative: Naive approach checking all paths would be exponential; this uses DFS with pruning negative sums for efficiency

Edge Cases

Empty tree (root is nil)

Returns minimum integer value or 0 depending on implementation; here returns MinInt64

DSA Go

if node == nil { return 0 }

All negative values in tree

Returns the largest (least negative) single node value as max path sum

DSA Go

left := max(dfs(node.Left), 0) // ignore negative sums

Single node tree

Returns the value of the single node as max path sum

DSA Go

if node == nil { return 0 }

When to Use This Pattern

When asked to find the maximum sum path in a tree that can start and end anywhere, use DFS with tracking max sums including both children and pruning negatives.

Common Mistakes

Mistake: Returning sum of both children upwards instead of only one child
Fix: Return node.Val plus max of left or right child sums to maintain valid path upwards

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

Summary

Finds the highest sum of values along any path in a binary tree.

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

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