Coding Interview Prep: Binary Tree Maximum Path Sum
Finding the maximum path sum in a Binary Tree.
Here we will go over Leetcode problem 124: Binary Tree Maximum Path Sum
The steps we must follow are:
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.
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 caseCalculate 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.