Binary Tree Maximum Path Sum is nothing but Maximum Subarray Sum?
As the title says we can use Kadane’s algorithm used for solving the maximum subarray sum for figuring out the maximum path sum for a binary tree.
Just for a quick refresher Kadane algorithm is basically calculating the maximum of all local maximums. Here local maximum or maximum ending at index i is nothing but the maximum sum of all subarrays ending at i.
globalMax ← Our answer
localMax ← Maximum at index i
Iterate through the array (nums) and for every index i:
localMax = max(nums[i], num[i] + localMax) → 1
globalMax = max(globalMax, localMax) → 2
In line 1 above we are updating localMax as max of sum of previous localMax and current index, and current index .
In line 2 we are just updating the globalMax comparing it to the new localMax.
So when we go through the array, globalMax gives us the maximum of all subarrays ending at different indexes and hence the maximum subarray sum overall.
The same concept can be reused to figure out the maximum path sum for a binary tree.
Like before we considered subarrays ending at different indexes, now that point of consideration becomes a different node of a tree.
A path will start from a leaf and go up 0 or more nodes to the highest node on the path and then come back down. That highest node is the lowest common ancestor of all nodes on this path and that is the node we consider like an index in the maximum subarray problem.
So the problem boils down to figuring out the maximum of all these nodes. We can keep a globalMax which will be our answer, the code will look something like this:
Short and clean, isn’t it!
Let’s try and understand this solution. For each node (the highest node of the path), we first calculate the maximum sum down in the left and right subtree. Note we consider it as a max of the sum and 0, to filter out any negative sums we might get, as they are not going to increase our current sum we just ignore them and use the root’s value (another instance of kadane’s algo at work!).
Next is the comparison with the global max, this is exactly the same as that in max subarray problem, we are comparing the result for the maximum of all paths with current node as the highest node and the maximum obtained till now.
Finally, we return the maximum sum down as max of sum down in the left and right subtree but the node’s value.
I hope my understanding of maximum sum path of a binary tree helped you out as well, please feel free to comment if you find ways to improve upon this solution or explanation!
