Be the first user to complete this post

  • 0
Add to List
Medium

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
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 RLS and RLS respectively.
  • Now at each node calculate sumCurrent =Max (RLS,  RLS, RLS + RLS + Root data) and update maxSoFar = sumCurrent if maxSoFar<sumCurrent
  • At each node return Max (RLS,  RLS ) +root.data. (return max path from the current node)
  • See the image below for better understanding
Maximum Sum path between two leaves Solution
 

Output:

Max Path Sum Between Two Leaves is 24