Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given a binary tree, Find the max­i­mum path sum from one leaf node to another.

Input: A binary tree.

Exam­ple:

Maximum Sum path between two leaves

Max­i­mum Sum path between two leaves

Approach:

  • Now we will cal­cu­late 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 vari­able say, “maxSoFar=0″ this will our final result.
  • Do pos­tOrder tra­ver­sal, This will give you result from left and right subtree
  • Now at each node cal­cu­ate sum­Cur­rent =Max of (result of leftSubtree,result of Right­Sub­tree, result of leftSubtree+result of Right­Sub­tree + Root data)
  • if(maxSoFar<sumCurrent) then max­So­Far = sumCurrent
  • At each node return max(result of leftSubtree,result of RightSubtree)+root.data;
  • See Pic­ture
Maximum Sum path between two leaves Solution

Max­i­mum Sum path between two leaves Solution

Com­plete Code:


Out­put:

Max Path Sum Between Two Leaves is 24

You may also like...

  • Sai Yashod­har 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);

    • tuto­ri­al­hori­zon

      Thanks Sai for find­ing the cor­ner case for which the code failed, i have fixed it, hope it will work for all the cases now. I encour­age you to find out more errors in this or other arti­cles, that’s how we can make it better.

      • Sai Yashod­har Vinay

        from col­lec­tions 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 par­ent:
        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 “Lev­el­Order : “,
        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 pos­si­ble sums
        print max(t.res2) #_______gives the maxSum

  • Van­dana Sharma

    what hap­pens in case of fol­low­ing trees -> Ide­ally max path sum should be 8 and 6 but code would return 6 and 4 respec­tively
    https://uploads.disquscdn.com/images/37c342ee068350b9aeb3bc422417fbb1bc607320d8df7f37b0804941db3cd47c.png

    To cor­rect this we should con­sider
    umCur­rent = Math.max(leftS+rightS+root.data , Math.max(leftS, rightS), leftS+root.data, rightS+root.data);