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.


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


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

Maximum Sum path between two leaves Solution

Complete Code:

public class MaxPathSumBwTwoLeaves {
public static int maxSoFar =0;
public int maxPathSum(Node root){
int leftS = maxPathSum(root.left);
int rightS = maxPathSum(root.right);
int sumCurrent;
if(leftS<0 && rightS<0){
sumCurrent =;
sumCurrent = Math.max( , Math.max(leftS, rightS));
// sumCurrent = Math.max( , Math.max(leftS, rightS));
maxSoFar = sumCurrent;
return Math.max(leftS,rightS);
else return 0;
public void inorder(Node root){
System.out.print(" " +;
public static void main(String args[]){
Node root = new Node(5);
root.left = new Node(1);
root.right = new Node(4);
root.left.left = new Node(6);
root.left.right = new Node(5);
root.left.right.left = new Node(2);
root.left.right.right = new Node(3);
root.left.left.left = new Node(9);
root.left.left.right = new Node(10);
root.right.left = new Node(11);
root.right.right = new Node(2);
root.right.right.right = new Node(8);
root.right.right.left = new Node(7);
root.right.right.right.left = new Node(1);
root.right.right.right.right = new Node(7);
root.right.right.right.right.left = new Node(12);
MaxPathSumBwTwoLeaves m = new MaxPathSumBwTwoLeaves();
System.out.println("Max Path Sum Between Two Leaves is " + maxSoFar);
class Node{
int data;
Node left;
Node right;
public Node (int data){ = data;
left = null;
right = null;


Max Path Sum Between Two Leaves is 24