Given a binary tree in which each node element contains a number. Find the maximum possible sum from one leaf node to another.
Example 1:
Input :
3
/ \\
4 5
/ \\
-10 4
Output: 16
Explanation :
Maximum Sum lies between leaf node 4 and 5.
4 + 4 + 3 + 5 = 16.
Example 2:
Input :
-15
/ \\
5 6
/ \\ / \\
-8 1 3 9
/ \\ \\
2 -3 0
/ \\
4 -1
/
10
Output : 27
Explanation:
The maximum possible sum from one leaf node
to another is (3 + 6 + 9 + 0 + -1 + 10 = 27)
Maximum Path Sum between 2 Leaf Nodes | Practice | GeeksforGeeks
/*
struct Node
{
int data;
struct Node* left;
struct Node* right;
Node(int x){
data = x;
left = right = NULL;
}
};
*/
int MPS(Node* root,int &res) {
if(!root)
return 0;
if(!root->left&&!root->right)
return root->data;
int ls=MPS(root->left,res);
int rs=MPS(root->right,res);
int temp;
if(root->left&&root->right)
{
temp=root->data+max(ls,rs);
int ans=root->data+ls+rs; //here we are not considering ans = max(temp,root->data+ls+rs). Understand with help of test case -9,6,-10 where it will give output -3 instead of -13
res=max(res,ans);
}
if(!root->left)
{
temp=root->data+rs;
}
else if(!root->right)
{
temp=root->data+ls;
}
return temp;
}
int maxPathSum(Node* root)
{
int res = INT_MIN;
int h=MPS(root, res);
if(root->left==NULL || root->right==NULL) //if either of the children of root is NULL then res will never be updated that's why we are finding max(res,h). Understand this with example 9,6,N
{
res=max(res,h);
}
return res;
}
// Time Complexity : O(n)
// Space Complexity : O(h) where h = height of tree