# 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:

```go
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:

```go
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`:

```go
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.