To find the maximum path sum in a binary tree, we can use a recursive approach. The idea is to traverse the tree in a bottom-up manner and calculate the maximum path sum for each node.
We define a helper function maxPathSumHelper(node) that takes a node as input and returns one value:
The maximum path sum starting from the given node, considering only the left or right child paths (if they are positive), or just the node’s value if both children have negative path sums.
Then we calculate the path sum for each node as they are being considered as root node, and compare with the maximum answer.
Finally, we call the helper function maxPathSumHelper(root) on the root of the binary tree to obtain the maximum path sum.