17MaximumPathSum.cpp

#include <bits/stdc++.h>
using namespace std;

//To find the diameter of a binary tree, we can think of every node as a potential `Curving Point` of the path along which we find the sum. The maximum sum of a path through a turning point (like a curve) can be found by adding the maximum sum achievable in the left subtree, the right subtree, and the value of the turning point.

struct TreeNode
{
 int data;
 struct TreeNode* left;
 struct TreeNode* right;

 TreeNode(int val)
 {
 data = val;
 left = NULL;
 right = NULL;
 }
 
};

int maxi = INT_MIN;

int findMaxPath(TreeNode* root,int maxi){
 if(root==NULL){
 return 0;
 }

 int leftMaxPath = max(0,findMaxPath(root->left,maxi));
 int rightMaxPath = max(0,findMaxPath(root->right,maxi));

 maxi = max(maxi,leftMaxPath+rightMaxPath + root->data);

 return max(leftMaxPath,rightMaxPath) + root->data;
}


int main(){
 struct TreeNode* root = new TreeNode(2);
 root->left = new TreeNode(5);
 root->left->left = new TreeNode(4);
 root->left->left->left = new TreeNode(3);
 root->left->left->right = new TreeNode(2);
 root->left->right = new TreeNode(5);
 root->right = new TreeNode(7);
 root->right->left = new TreeNode(9);
 root->right->left->right = new TreeNode(2);
 root->right->left->right->right = new TreeNode(4);
 root->right->left->right->left = new TreeNode(1);
 root->right->left->left = new TreeNode(3);
 root->right->right = new TreeNode(7);
 


}