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
Complete Code:
Output:
Max Path Sum Between Two Leaves is 24
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
what happens in case of following trees -> Ideally max path sum should be 8 and 6 but code would return 6 and 4 respectively
https://uploads.disquscdn.com/images/37c342ee068350b9aeb3bc422417fbb1bc607320d8df7f37b0804941db3cd47c.png
To correct this we should consider
umCurrent = Math.max(leftS+rightS+root.data , Math.max(leftS, rightS), leftS+root.data, rightS+root.data);