# 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

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

Maximum Sum path between two leaves Solution

Complete Code:

Output:

`Max Path Sum Between Two Leaves is 24`

__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

#### You may also like...

• Sai Yashodhar Vinay

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

• tutorialhorizon

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.

• Sai Yashodhar Vinay

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

• Vandana Sharma

what happens in case of following trees -> Ideally max path sum should be 8 and 6 but code would return 6 and 4 respectively