Max path sum from node to node

#1

This code would fail right if we have a negative node present at the root?

#2

No, it works correct for even negative values.

#3

This code doestnt work for all negative nodes

#4

if the tree is [-2 ,-1] then we get the answer as 0 but answer should be -1 this is an edge case not handled by the code

#5

It depends on what the question wants, according to the code it seems like selecting no node is an acceptable answer.

In case you want the answer as -1, just don’t take max with 0.

#6


class Solution {
public:

pair<int,int> helper(TreeNode* root){

    pair<int,int>p;
    p.first=0;
    p.second=0;
 
    if(root==NULL){

       return p;
    
    }

   pair<int,int>l=helper(root->left);
   pair<int,int>r=helper(root->right);

   int op1=root->val;
   int op2=root->val+l.second;
   int op3=root->val+r.second;
   int op4=root->val+l.second+r.second;

   int curr_ans_through_root=max(op1,max(op2,max(op3,op4)));
   p.second=max(l.second,max(0,r.second))+root->val;
   p.first=max(l.first,max(curr_ans_through_root,r.first));
   return p;

}

int maxPathSum(TreeNode* root) {
  
    if(root->left==NULL && root->right==NULL){

       return root->val;
    
    }
  
    pair<int,int>p=helper(root);
    return p.first;
}

};

PLz suggest what change to make here in this code to make it work…if i remove comparison with 0 i stilll get wrong answer.correct the code plz

#7

make this change

    pair<int, int>p;
    p.first = -1e9;
    p.second = -1e9;