Maximum path sum in a binary tree
Given a binary Tree find the maximum path sum. The path may start and end at any node in the tree.
Input:
The first and the only argument contains a pointer to the root of binary tree.
Output:
Return an integer representing the maximum sum path.
Example with explanation:
Input:
6
/ \
3 9
Output:
18
(3->6->9), since all are positive integer,
we should consider all nodes sum.
Input:
-14
/ \
-26 -36
Output:
-14
The path sum is maximum at node (-14).
we will use the following concept.
For each node there can be four ways that the maximum sum path goes through the node:
we will initialize the resultant maximum sum variable res with INT_MIN, then we will use an ampersand operator for that variable and keep changing it with the following cases: we keep track of four paths and pick up the max one in the end. An important thing to note is, the root of every subtree need to return maximum path sum such that at most one child of root is involved. This is needed for the parent function call.
In the below code, this sum is stored in 'temp' and returned by the recursive function.
Standard Node:
We will use the above node for further operation.
Pseudo Code:
Time Complexity for above code is O(n).
C++ Implementation:
Output