Maximum Path Sum in Binary Tree in DSA Go - Build from Scratch

Maximum Path Sum in Binary Tree

📖 Scenario: You are working on a program that analyzes a binary tree representing a network of connected nodes. Each node has a value that can be positive or negative. Your task is to find the maximum sum of values along any path in the tree. A path can start and end at any node, but it must follow parent-child connections.

🎯 Goal: Build a Go program that creates a binary tree, sets a variable to track the maximum path sum, implements a recursive function to find the maximum path sum, and prints the final maximum path sum.

📋 What You'll Learn

Create a binary tree with the exact structure and values given

Create a variable called maxSum to track the maximum path sum

Write a recursive function called maxPathSumHelper that calculates the maximum path sum

Print the value of maxSum after processing the tree

💡 Why This Matters

🌍 Real World

Finding maximum path sums in trees is useful in network analysis, game development, and decision-making systems where the best route or combination needs to be found.

💼 Career

Understanding tree traversal and recursive algorithms is essential for software engineering roles, especially those involving data structures, algorithms, and system design.

1

Create the Binary Tree Structure

Create a struct type called TreeNode with fields Val int, Left *TreeNode, and Right *TreeNode. Then create the binary tree with root node value 1, left child 2, and right child 3. Assign the left child of node 2 to 4 and right child to 5. Assign the right child of node 3 to 6.

DSA Go

// Define TreeNode struct and create the binary tree as described
// Your code here

Hint

Define the TreeNode struct first. Then create nodes and link them as left and right children exactly as described.

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 int(^uint(0) >> 1) * -1 - 1.

DSA Go

package main

import "fmt"

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

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}

    // Create maxSum variable initialized to smallest int
    // Your code here
}

Hint

Use bitwise operations to get the smallest int value in Go and assign it to maxSum.

3

Implement Recursive Function to Find Maximum Path Sum

Write a recursive function called maxPathSumHelper that takes a pointer to TreeNode and a pointer to int called maxSum. The function returns an int. It should calculate the maximum path sum starting from the current node and update *maxSum if a larger path sum is found. Use the logic: calculate left and right max sums recursively, ignore negative sums by comparing with zero, update *maxSum with the sum of node value plus left and right max sums, and return the node value plus the maximum of left or right max sums.

DSA Go

package main

import "fmt"

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

func maxPathSumHelper(node *TreeNode, maxSum *int) int {
    // Your code here
}

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}

    maxSum := int(^uint(0) >> 1) * -1 - 1

    // Call maxPathSumHelper here
    // Your code here
}

Hint

Use recursion to find max sums from left and right children. Ignore negative sums by comparing with zero. Update *maxSum if current path sum is larger. Return max path sum including current node and one child.

4

Print the Maximum Path Sum

In the main function, after calling maxPathSumHelper, print the value of maxSum using fmt.Println(maxSum).

DSA Go

package main

import "fmt"

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

func maxPathSumHelper(node *TreeNode, maxSum *int) int {
    if node == nil {
        return 0
    }

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

    currentSum := node.Val + leftMax + rightMax
    if currentSum > *maxSum {
        *maxSum = currentSum
    }

    return node.Val + max(leftMax, rightMax)
}

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

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}

    maxSum := int(^uint(0) >> 1) * -1 - 1

    maxPathSumHelper(root, &maxSum)

    // Print maxSum
    // Your code here
}

Hint

Use fmt.Println(maxSum) to print the maximum path sum after the recursive call.