# 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:

• 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)+root.data;
• See Picture

Complete Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class MaxPathSumBwTwoLeaves { public static int maxSoFar =0; public int maxPathSum(Node root){ if(root!=null){ int leftS = maxPathSum(root.left); int rightS = maxPathSum(root.right); int sumCurrent; if(leftS<0 && rightS<0){ sumCurrent = root.data; }else{ sumCurrent = Math.max(leftS+rightS+root.data , Math.max(leftS, rightS)); } // sumCurrent = Math.max(leftS+rightS+root.data , Math.max(leftS, rightS)); if(maxSoFar

Output:

Max Path Sum Between Two Leaves is 24

### 4 thoughts on “Given a binary tree, Find the Maximum Path Sum between Any Two Leaves”

1. Here code is not correct.I have a counter example.Run the code for this tree.
Answer should be 50000 but here the code returns less than 50000

Node root = new Node(50000);

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);

• Thanks Sai for finding the corner case for which the code failed, i have fixed it, hope it will work for all the cases now. I encourage you to find out more errors in this or other articles, that’s how we can make it better.

• from collections import deque
class node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
class tree:
def __init__(self,n):
self.root=n
self.maxPath=0
self.res1=[]
def insert(self,n1):
n=self.root
parent=None
while n:
parent=n
if n.data==n1.data:
return
elif n.data>n1.data:
n=n.left
else:
n=n.right
if parent:
if parent.data>n1.data:
parent.left=n1
else:
parent.right=n1
def levelOrder(self):
n=self.root
q=deque()
if n:
q.append(n)
print “LevelOrder : “,
while 1:
count=len(q)
if count==0:
break
while count>0:
e=q.popleft()
print e.data,
if e.left:
q.append(e.left)
if e.right:
q.append(e.right)
count-=1
print ”
def anyTwoLeavesMaxSum(self,n):
if n:
left=self.anyTwoLeavesMaxSum(n.left)
right=self.anyTwoLeavesMaxSum(n.right)
currSum=max(left+n.data,n.data+right,left+n.data+right)
if self.checkLeafNode(n.left)==False:
currSum=max(left,currSum)
if self.checkLeafNode(n.right):
currSum=max(right,currSum)
self.res2.append(currSum)
return max(left,right)+n.data
return 0
def checkLeafNode(self,n):
if n and n.left==None and n.right==None:
return True
return False
import math
l=5
n=int(math.pow(2,l))
Nodes=[node(i) for i in range(n)]
t=tree(Nodes[1])
for i in range(1,n/2):
Nodes[i].left=Nodes[2*i]
Nodes[i].right=Nodes[2*i+1]
#Nodes[1].left=None
Nodes[2].right=None
Nodes[4].left=None
Nodes[12].left=None;Nodes[12].right=None
Nodes[13].left=None;Nodes[13].right=None
Nodes[7].left=None
Nodes[15].left=None;Nodes[15].right=None;

t.levelOrder();
t.anyTwoLeavesMaxSum(t.root)
print t.res2 #_____the list of possible sums
print max(t.res2) #_______gives the maxSum