# Binary Tree Maximum Path Sum

Another trees related problem :)

A **path** in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence **at most once**. Note that the path does not need to pass through the root.

The **path sum** of a path is the sum of the node’s values in the path.

Given the `root`

of a binary tree, return *the maximum **path sum** of any **non-empty** path*.

I think these tree related problems are quite easier compared to other data structures.

Tree traversals are only BFS or DFS (pre-order, in-order and post-order). If we know what traversal to follow, problem is solved.

For this problem, we should follow post-order traversal as we need subtrees paths.

Write a recursive post order function, which does calculating of the path sum and updating max path sum then return the max path sum.

path sum of node = node value + left subtree gain

+ right subtree gain

gain of node = its node value [+ max(left/right subtree not both)]

Below is the solution:

`/**`

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

/* Its a post order function,

calculating the pathsum and updating max val

then return the max pathsum

path sum includes node values + left subtree path sum

+ right subtree path sum

while return the gain, gain can include

its node value [+ max(left/right subtree not both)]

*/

int max_gain(struct TreeNode* nd, int *mg){

if (!nd)

return 0;

int lg, rg;

lg = max_gain(nd->left, mg);

rg = max_gain(nd->right, mg);

lg = (lg < 0) ? 0 : lg;

rg = (rg < 0) ? 0 : rg;

if ((*mg) < (nd->val+lg+rg))

(*mg) = nd->val+lg+rg;

if (lg > rg) rg = lg;

return(nd->val+ rg);

}

int maxPathSum(struct TreeNode* root){

int g=0, mg=0;

if (!root) return 0;

mg = root->val;

g = max_gain(root, &mg);

return mg;

}