I am trying to solve this Leetcode problem: Binary Tree Maximum Path Sum. I know there are a lot of SO answers for this question. But I could not find anything related to my issue. So, before diving into the code, I want to give a high-level overview of how I wrote the algorithm.
If I am at a particular node, I considered the following cases.
Case 1: The maximum path is somewhere inside the left subtree (not including the current node)
Case 2: The maximum path is somewhere inside the right subtree (not including the current node)
Case 3: The maximum path starts from the current node and ends somewhere in the left subtree
Case 4: The maximum path starts from the current node and ends somewhere in the right subtree
Case 5: The maximum path is the current node itself.
Case 6: The maximum path starts somewhere in the left subtree, goes through the current node, and ends somewhere in the right subtree.
And here is the code:
var maxPathSum = function(root) {
if (root.left === null && root.right === null) {
return root.val;
}
// Case 1: Max sum is in the left subtree (not including the root)
let leftPathSum = 0;
if (root.left) {
leftPathSum = maxPathSum(root.left);
}
// Case 2: Max sum is in the right subtree (not including the root)
let rightPathSum = 0;
if (root.right) {
rightPathSum = maxPathSum(root.right);
}
// Case 3: root + leftPathSum
let leftSumWithRoot = leftPathSum + root.val;
// Case 4: root + rightPathSum
let rightSumWithRoot = rightPathSum + root.val;
let maxWithRoot = Math.max(leftSumWithRoot, rightSumWithRoot);
let maxWithoutRoot = Math.max(leftPathSum, rightPathSum);
let maxSoFar = Math.max(maxWithRoot, maxWithoutRoot);
// Case 5: Root with alone
maxSoFar = Math.max(maxSoFar, root.val);
// Case 6: Max path goes through the root
let maxThroughRoot = leftSumWithRoot + rightSumWithRoot - root.val;
return Math.max(maxThroughRoot, maxSoFar);
};
I am getting some of the test cases passing, some are not, especially the ones which have negative values. I know my algorithm most probably has issues, but can someone help me where my thinking going in the wrong direction. I saw different solutions to this problem. In some solutions, they are comparing the maxPathSum(node. left) and maxPathSum(node.right) with 0 Is the issue related to this? Also, in some other solutions, they are not considering the maxPathSum that is inside the left and right subtree. Shouldn't I do that? If someone just gives me an idea of where I am doing wrong, I would be really grateful. Thanks in advance.
Your code is failing in this input: [-2,-1]
graph looks like this:
-2
/
-1
So, let maxWithoutRoot = Math.max(leftPathSum, rightPathSum); will be 0. Then maxSoFar will be zero so eventaully your output is 0. If I organize your code :
var maxPathSum = function(root) {
let res=root.val
function dfs(node){
if (node===null){
return 0
}
let left=dfs(node.left)
let right=dfs(node.right)
// ignoring negatives. looking for max, so if left or right is negative, do not add it
let leftMax=Math.max(left,0)
let rightMax=Math.max(right,0)
res=Math.max(node.val+leftMax+rightMax,res)
return node.val+Math.max(leftMax,rightMax)
}
dfs(root)
return res
};