Maximum Sum Path Of A Binary Tree

Problem Link:

1. https://www.codingninjas.com/studio/problems/maximum-sum-path-of-a-binary-tree_1214968

2. https://leetcode.com/problems/binary-tree-maximum-path-sum/

Hint:

Code:

int helper(BinaryTreeNode<int> *root, int &maxSum){

    if(root==NULL){
        return 0;
    }

    int leftPathSum = helper(root->left, maxSum);
    int rightPathSum = helper(root->right, maxSum);

    int maxi = max(leftPathSum, rightPathSum);

    if(leftPathSum>=0 && rightPathSum>=0){

        maxSum = max(maxSum, leftPathSum+rightPathSum+root->data);
        return root->data+maxi;
    }

    else if(leftPathSum<0 && rightPathSum<0){

        maxSum = max(maxSum, root->data);
        return root->data;
    }

    else{
        maxSum = max(maxSum, maxi+root->data);
        return maxi+root->data;
    }
}

int maxPathSum(BinaryTreeNode<int> *root)
{
    // Write your code here
    int maxSum = -1e9;
    helper(root,maxSum);

    return maxSum;
}