← Back to DevBytes
Go August 05, 2026 9 min read

Solving Binary Tree Maximum Path Sum in Go: Step-by-Step Guide

Introduction to Binary Tree Maximum Path Sum

The Binary Tree Maximum Path Sum problem is one of the most classic and challenging tree-based algorithm problems you will encounter. Given a binary tree where each node contains an integer value (which can be positive, negative, or zero), the goal is to find the maximum sum of any path connecting a sequence of nodes. A path in this context must follow parent-child connections, can start and end at any node, and must contain at least one node.

This problem frequently appears in technical interviews at top-tier companies and on platforms like LeetCode (problem #124). It tests your understanding of tree traversal, recursion, and the ability to carefully reason about how local computations contribute to a global result.

What Is a Path in a Binary Tree?

Before diving into the solution, it is essential to clarify what constitutes a valid path. A path is a sequence of nodes where each pair of adjacent nodes has a parent-child relationship. The path does not need to pass through the root, and it does not need to go from a leaf to another leaf. It can be as short as a single node or as long as a full traversal from one leaf down through a common ancestor to another leaf.

For example, consider the following tree:

      1
     / \
    2   3

The possible paths include: [1], [2], [3], [2, 1], [3, 1], and [2, 1, 3]. The maximum path sum here is 6, achieved by the path [2, 1, 3].

Why This Problem Matters

This problem matters because it forces you to distinguish between two related but distinct concepts:

Mastering this distinction will sharpen your recursive thinking and prepare you for many other tree and graph problems, including diameter calculations, subtree sum problems, and dynamic programming on trees.

Understanding the Core Idea

The key insight is that when we process a node during a post-order traversal, we need to compute two things:

At each node, we update the global maximum with the "turning" path sum, and we return the "extending" path sum to the parent. This separation is what makes the algorithm both correct and efficient.

Step-by-Step Algorithm

Step 1: Define the Tree Node

In Go, we define a binary tree node using a struct with a value and pointers to left and right children.

package main

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

Step 2: Set Up a Global Maximum

We need a variable to track the maximum path sum found so far. Since node values can be negative, we initialize this variable to the smallest possible integer value using math.MinInt64.

import "math"

var maxSum int = math.MinInt64

Step 3: Write the Recursive Helper

The helper function performs a post-order traversal. For each node, it recursively computes the maximum gain from the left and right subtrees. If a subtree's gain is negative, we treat it as zero because including a negative branch would only reduce the path sum.

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

    // Recursively get the max gain from left and right subtrees.
    // Negative gains are clamped to 0 because we can choose not to include them.
    leftGain := max(maxGain(node.Left), 0)
    rightGain := max(maxGain(node.Right), 0)

    // The price of the path that "turns" at this node (uses both children).
    turningPath := node.Val + leftGain + rightGain

    // Update the global maximum if this turning path is better.
    if turningPath > maxSum {
        maxSum = turningPath
    }

    // For the parent, we can only extend through one child branch.
    return node.Val + max(leftGain, rightGain)
}

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

Step 4: Expose the Public Function

The public function resets the global maximum and kicks off the recursion from the root.

func maxPathSum(root *TreeNode) int {
    maxSum = math.MinInt64
    maxGain(root)
    return maxSum
}

Complete Working Example

Below is a complete, runnable Go program that constructs a sample tree and prints the maximum path sum.

package main

import (
    "fmt"
    "math"
)

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

var maxSum int

func maxPathSum(root *TreeNode) int {
    maxSum = math.MinInt64
    maxGain(root)
    return maxSum
}

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

    leftGain := max(maxGain(node.Left), 0)
    rightGain := max(maxGain(node.Right), 0)

    turningPath := node.Val + leftGain + rightGain
    if turningPath > maxSum {
        maxSum = turningPath
    }

    return node.Val + max(leftGain, rightGain)
}

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

func main() {
    // Construct the tree:
    //       -10
    //       /  \
    //      9   20
    //         /  \
    //        15   7
    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}

    result := maxPathSum(root)
    fmt.Println("Maximum Path Sum:", result) // Output: 42
}

In this example, the maximum path is [15, 20, 7], which sums to 42. Notice that the root node -10 is excluded because including it would reduce the total sum.

Tracing Through the Execution

To build intuition, let us trace the recursion on the example tree:

The final answer is 42, which matches our expectation.

Complexity Analysis

The algorithm visits each node exactly once, so the time complexity is O(n), where n is the number of nodes in the tree. The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case of a skewed tree, this becomes O(n); for a balanced tree, it is O(log n).

Best Practices

Avoid Global Mutable State in Production

Using a package-level variable like maxSum works fine for a coding challenge, but in production code it is fragile and not safe for concurrent use. A cleaner approach is to pass a pointer to the maximum value or to return both the local gain and the best path sum from the recursive function.

func maxPathSumClean(root *TreeNode) int {
    _, best := dfs(root)
    return best
}

func dfs(node *TreeNode) (gain int, best int) {
    if node == nil {
        return 0, math.MinInt64
    }

    leftGain, leftBest := dfs(node.Left)
    rightGain, rightBest := dfs(node.Right)

    leftGain = max(leftGain, 0)
    rightGain = max(rightGain, 0)

    turning := node.Val + leftGain + rightGain
    best = max(turning, max(leftBest, rightBest))

    gain = node.Val + max(leftGain, rightGain)
    return gain, best
}

This version avoids global state entirely and is easier to test and reason about.

Handle Edge Cases Explicitly

Always consider edge cases such as a tree with a single node, a tree where all values are negative, and a tree that is completely skewed. The algorithm above handles all of these correctly because we initialize maxSum to the smallest possible integer and always consider the node's own value as a candidate path.

Use Go's Built-in Max in Newer Versions

If you are using Go 1.21 or later, you can use the built-in max function instead of defining your own. This reduces boilerplate and makes the code more idiomatic.

Test Thoroughly

Write unit tests covering various scenarios:

func TestMaxPathSum(t *testing.T) {
    tests := []struct {
        name string
        root *TreeNode
        want int
    }{
        {"single positive", &TreeNode{Val: 5}, 5},
        {"single negative", &TreeNode{Val: -3}, -3},
        {"simple tree", buildSimpleTree(), 6},
        {"complex tree", buildComplexTree(), 42},
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            got := maxPathSumClean(tt.root)
            if got != tt.want {
                t.Errorf("got %d, want %d", got, tt.want)
            }
        })
    }
}

Common Mistakes to Avoid

Variations and Follow-Up Problems

Once you understand this problem, you can apply the same dual-return technique to related problems:

Conclusion

The Binary Tree Maximum Path Sum problem elegantly demonstrates how a single recursive traversal can solve a seemingly complex problem by carefully separating local contributions from global candidates. By clamping negative gains, computing turning paths at each node, and returning only single-branch extensions to parents, you arrive at an efficient O(n) solution. Whether you are preparing for interviews or writing production Go code, mastering this pattern of dual-purpose recursion will serve you well across a wide range of tree and graph challenges. Remember to avoid global mutable state in real applications, test edge cases thoroughly, and leverage Go's modern features to keep your code clean and idiomatic.

— Ad —

Google AdSense will appear here after approval

← Back to all articles