Maximum Path sum in tree

Maximum Path sum in tree

  August 18, 2017    

---

Explanation:

Max path will be either root node/(left /right subtree)+root 
Or root.data +left subtree max+right subtree max

So we are traversing with LR method and calculating them.

Code:

int findMaxUtil(Node* root, int &res)
{
    if(root==NULL)
    return 0;
    int l=findMaxUtil(root->left,res);
    int r=findMaxUtil(root->right,res);
    int mx1=max(max(l,r)+root->data,root->data);
    int mx=max(l+r+root->data,mx1);
     res=max(mx,res);
    return mx1;
}