Binary Tree Maximum Path Sum

Jyothi
2 min readApr 7, 2022

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

--

--