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.
Learn more about bidirectional 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<sumCurrent){ | |
maxSoFar = sumCurrent; | |
} | |
return Math.max(leftS,rightS)+root.data; | |
} | |
else return 0; | |
} | |
public void inorder(Node root){ | |
if(root!=null){ | |
inorder(root.left); | |
System.out.print(" " + root.data); | |
inorder(root.right); | |
} | |
} | |
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(); | |
m.maxPathSum(root); | |
System.out.println("Max Path Sum Between Two Leaves is " + maxSoFar); | |
//m.inorder(root); | |
} | |
} | |
class Node{ | |
int data; | |
Node left; | |
Node right; | |
public Node (int data){ | |
this.data = data; | |
left = null; | |
right = null; | |
} | |
} |
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);