Coding Interview Prep: Binary Tree Maximum Path Sum

Here we will go over Leetcode problem 124: Binary Tree Maximum Path Sum

The steps we must follow are:

1. Define a helper function that calculates the maximum path sum with the highest node being the root of the path and updates the global maximum path sum.

2. Use this helper function recursively for each node

First we define a maxPathSum, which will call our helper function maxGain on the root node, and will recursively call itself on the roots children. So maxPathSum should look like this:

func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt32
    maxGain(root, &maxSum)
    return maxSum
}

• Initialize the maxSum, using math.MinInt32, the minimum possible value for a 32-bit integer

Now for the recursive maxGain function:

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

    // Recursively call maxGain on the left and right children
    leftGain := max(0, maxGain(node.Left, maxSum))
    rightGain := max(0, maxGain(node.Right, maxSum))

    // The price of the current node is itself plus max gain from left and right children
    priceNewPath := node.Val + leftGain + rightGain

    // Update maxSum if priceNewPath is greater
    *maxSum = max(*maxSum, priceNewPath)

    // Return the maximum gain if we continue the same path
    return node.Val + max(leftGain, rightGain)
}

• we handle errors or nonexistent nodes by first checking if the node is nil, returning 0 if that is the case

• Calculate the maximum gain from the left and right subtrees. We ensure non-negative values by taking the max between 0 and maxGain

• Update the global maximum path sum (`maxsum`) by considering the path passing through the current node and both its children.

• Return the maximum gain obtained by including the current node and one of its children

Lastly we define a utility function for calculating the max between two numbers, max:

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

And that's it! With these functions, we are able to find the maximum path sum of a Binary tree.