Be the first user to complete this post

  • 0
Add to List
Medium

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.

Input: A binary tree.

Example:

Maximum Sum path between two leaves
Maximum Sum path between two leaves

Approach:

  1. Now we will calculate the max path sum between two leaves node
  2. So our max path will be either on the left sub tree OR
  3. Our max path will be either on the right sub tree OR
  4. Our max path will have some part in left and some part in right and passes through through the root
  5. Take a variable say, "maxSoFar=0" this will our final result.
  6. Do postOrder traversal, This will give you result from left and right subtree
  7. Now at each node calcuate sumCurrent =Max of (result of leftSubtree,result of RightSubtree, result of leftSubtree+result of RightSubtree + Root data)
  8. if(maxSoFar<sumCurrent) then maxSoFar = sumCurrent
  9. At each node return max(result of leftSubtree,result of RightSubtree)+root.data;
  10. See Picture
Maximum Sum path between two leaves Solution

Code:


Output:

Max Path Sum Between Two Leaves is 24



Also Read: