65. Given a binary tree, Find the Maximum Path Sum between Any Two Leaves

Objective: Given a binary tree, find the maximum path sum from one leaf node to another.

Example:

Maximum Sum path between two leaves

Approach:

Max path will be either on the
- Left subtree
- Right subtree
- Some parts are on the left and some parts are on the right and pass through the root
The idea is to calculate the maximum path sum at each node, keep track of it, and return at the end.
Take a variable say, maxSoFar=0 this will be the final result.
Do postOrder traversal, This will give results from the left and right subtree, call it LeftS and RightS respectively.
Now at each node calculate sumCurrent =Max (LeftS, RightS, LeftS + RightS + Root data) and update maxSoFar = sumCurrent if maxSoFar<sumCurrent
At each node return Max (LeftS, RightS ) +root.data. (return max path from the current node)
See the image below for better understanding

Output:

Max Path Sum Between Two Leaves is 24