Here is a correct max path sum algorithm
export function maxPathSum(tree: BinaryTree): number {
let currMax = -Infinity;
const helper = (node: BinaryTree | null): number => {
if (!node) return 0;
const leftVal = Math.max(helper(node.left), 0);
const rightVal = Math.max(helper(node.right), 0);
currMax = Math.max(leftVal + rightVal + node.value, currMax);
return Math.max(leftVal, rightVal) + node.value;
}
helper(tree);
return currMax;
}
I do not understand why I am doing
const leftVal = Math.max(helper(node.left), 0);
Negative numbers are part of the path. To exclude negative numbers would be to get the wrong sum, right? Can someone explain why this logic is correct.
To exclude negative numbers would be to get the wrong sum, right?
Yes, it would indeed be wrong. But, if you look closely at this code,
const leftVal = Math.max(helper(node.left), 0);
you are not comparing current node value or left/right node value with zero, you are actually comparing the output of helper for left subtree and right subtree. And then, if you see that the output of left or right subtree is lesser than zero then there is no need to include it in our "max sum" path.