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:

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

Related Problems:

- Printing Nodes without Siblings in a Binary Tree Beginner
- Reverse a Linked List Using Recursion Medium
- Locate the Farthest Left Node on the Bottom Level Medium
- Print all steps to convert one string to another string Medium
- Get the Sum of all left leaves in a Binary tree Beginner