Given a binary tree, find out its maximum path sum.
A path should have at least one node and does not need to go through the root of the tree
Example, the tree given below the maximum path sum is 41 (11 + 8 + 10 + 12).
With any tree problem, it really helps to think recursively.
We can observe the following for any given node, maximum path sum through that node is maximum of the following values:
1. value of the node
2. sum of node + left subtree max path sum
3. sum of node + right subtree max path sum
4. sum of node + left subtree max path sum + right subtree max path sum
We can use this to implement the solution.