The website GeeksforGeeks has presented a solution for the problem of Maximum path sum for a binary tree. The question is as follows:
Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree.
The core of the solution is as follows:
int findMaxUtil(Node node, Res res)
{
if (node == null)
return 0;
// l and r store maximum path sum going through left and
// right child of root respectively
int l = findMaxUtil(node.left, res);
int r = findMaxUtil(node.right, res);
// Max path for parent call of root. This path must
// include at-most one child of root
int max_single = Math.max(Math.max(l, r) + node.data,
node.data);
// Max Top represents the sum when the Node under
// consideration is the root of the maxsum path and no
// ancestors of root are there in max sum path
int max_top = Math.max(max_single, l + r + node.data);
// Store the Maximum Result.
res.val = Math.max(res.val, max_top);
return max_single;
}
int findMaxSum() {
return findMaxSum(root);
}
// Returns maximum path sum in tree with given root
int findMaxSum(Node node) {
// Initialize result
// int res2 = Integer.MIN_VALUE;
Res res = new Res();
res.val = Integer.MIN_VALUE;
// Compute and return result
findMaxUtil(node, res);
return res.val;
}
Res has the following definition:
class Res {
public int val;
}
I am confused about the reasoning behind these lines of code:
int max_single = Math.max(Math.max(l, r) + node.data, node.data);
int max_top = Math.max(max_single, l + r + node.data);
res.val = Math.max(res.val, max_top);
return max_single;
I believe the code above follows this logic but I do not understand WHY this logic is correct or valid:
For each node there can be four ways that the max path goes through the node:
- Node only
- Max path through Left Child + Node
- Max path through Right Child + Node
- Max path through Left Child + Node + Max path through Right Child
In particular, I do not understand why max_single is being returned in the function findMaxUtil when we the variable res.val contains the answer we are interested in. The following reason is given on the website but I do not understand it:
An important thing to note is, root of every subtree need to return maximum path sum such that at most one child of root is involved.
Could someone provide an explanation for this step of the solution?
