Given a binary tree, Find the Maximum Path Sum between Any Two Leaves

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

   Reply

   • 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.

     Reply

     • 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

       Reply

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

   Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.