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

by · November 18, 2014

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

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

Google Microsoft Amazon Facebook more..

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

Tags:

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

Follow:

Select level

Beginner
Intermediate
Expert

Top Companies

Google
Microsoft
Amazon
Facebook
More…

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 1,264 other subscribers

Follow me on Twitter

%d bloggers like this: