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:

- In a Binary Tree, Check if Two nodes has the same parent or are siblings Medium
- Find Paths with Sum in Binary Tree Medium
- Convert binary tree to its Sum tree Medium
- Round Price Problem Hard
- Find the Maximum Depth OR Height of a Binary Tree Beginner