Do not understand the solution for the Binary Tree Maximum Path Sum problem

You're missing the value of res.val. The algorithm is trying to explore the whole tree, using res.val equal to the maximum path length explored up till then. In each step it iterates recursively across the children and updates res.val with the maximum path length, if higher than the one already present.

Proof:

Assume your algorithm works with trees with height n. For trees with height n+1 there's a root and 2 sub trees of height n. Also consider that findMaxUtil works fine for i<=n and will return the maximum path, starting with the partial root of the sub trees.

So the maximum path in your tree with height n+1 is calculated as follows

1. findMaxUtil(subtree1)
2. findMaxUtil(subtree2)
3. findmaxUtil(subtree1)+root.data
4. findmaxUtil(subtree2)+root.data
5. findmaxUtil(subtree1)+findmaxUtil(subtree2)+root.data
6. res.val

And finally the result is: findmaxUtil(newTree)=max(items 1:6).

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 problem is that findMaxUtil() really does two things: it returns largest sum of the tree that it's applied to, and it updates a variable that keeps track of the largest sum yet encountered. There's a comment to that effect in the original code, but you edited it out in your question, perhaps for brevity:

// This function returns overall maximum path sum in 'res' 
// And returns max path sum going through root. 
int findMaxUtil(Node node, Res res) 

Because Java passes parameters by value, but every object variable in Java implicitly references the actual object, it's easy to miss the fact that the Res that's passed in the res parameter may be changed by this function. And that's exactly what happens in the lines you asked about:

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;

That first line finds the maximum of the node itself or the node plus the greatest subtree, and that result is the max path sum going through root. Returning that value on the last line is one thing that this function does. The second and third lines look at that value and consider whether either it or the path that includes both children is larger than any previously seen path, and if so, it updates res, which is the other thing this function does. Keep in mind that res is some object that exists outside the method, so changes to it persist until the recursion stops and findMaxSum(Node), which started the whole thing, returns the res.val.

So, getting back to the question at the top, the reason that the findMaxUtil returns max_single is that it uses that value to recursively determine the max path through each subtree. The value in res is also updated so that findMaxSum(Node) can use it.