3 months ago

Swapnil Soni • 0

Vasco da Gama

Max path sum in binary tree

class Solution {
  public:
    int solve(Node* root,int &maxi){
        if(!root) return 0;
        int left = solve(root->left,maxi);
        int right = solve(root->right,maxi);
        maxi = max(maxi,left+right+root->data);
        return max(0,root->data+max(left,right));
    }
    //Function to return maximum path sum from any node in a tree.
    int findMaxSum(Node* root)
    {   
        int maxi = -1e9;
        solve(root,maxi);
        return maxi;
    }
};