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:

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

Run This Code

Code:

Output:

Max Path Sum Between Two Leaves is 24

Also Read:

- In a Binary Tree, Check if Two nodes has the same parent or are siblings Medium
- Reverse a Linked List Beginner
- Divide and Conquer - Rearrange array elements in special order Medium
- Backtracking - Search a Word In a Matrix Hard
- In a number, add digits until it becomes a single digit Beginner
- Backtracking - N Queens Problem Hard
- Print a path from Root to Node in Binary Tree Medium
- Find the number of distinct Islands OR connected components. Hard