(96). 27.16. MAX SUM PATH FROM ONE NODE TO ANOTHER IN BINARY TREE - anishsingh90/Data_Structure_And_Algorithm_In_Cpp_github.io GitHub Wiki

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

struct Node{ int data; Node *left, *right;

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

};

int maxPathSumUtil(Node* root, int &ans){ if(root == NULL){ return 0; }

int left = maxPathSumUtil(root->left, ans);
int right = maxPathSumUtil(root->right, ans);

int nodeMax = max(max(root->data, root->data + left + right), max(root->data + left, root->data + right));

ans = max(ans, nodeMax);
int singlePathSum = max(root->data, max(root->data+left, root->data + right));
return singlePathSum;

}

int maxPathSum(Node* root){ int ans = INT_MIN; maxPathSumUtil(root, ans); return ans; }

int main(){

/*
      1
     / \
    2   3
   /     \
  4       5
*/



Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->right = new Node(5);

//max path sum cout << "Max path sum: "; cout << maxPathSum(root); // 15 = 4+5+2+3+1

return 0;

}

/* OUTPUT: Max path sum: 15 */