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…

Subscribe for New Posts ( No Spams!!)

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

Join 1,294 other subscribers

Follow me on Twitter

%d bloggers like this: