# 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;}`

--

--