Reputation: 71

Maximum Path Sum between 2 Leaf Nodes(GeeksForGeeks)

Given a binary tree in which each node element contains a number. Find the maximum possible sum from one leaf node to another.

Example 1:

Explanation : Maximum Sum lies between leaf node 4 and 5. 4 + 4 + 3 + 5 = 16.

Example 2:

Input :    
            -15                               
         /      \                          
        5         6                      
      /  \       / \
    -8    1     3   9
   /  \              \
  2   -3              0
                     / \
                    4  -1
                       /
                     10  

Output :  27

Explanation: The maximum possible sum from one leaf node to another is (3 + 6 + 9 + 0 + -1 + 10 = 27)

This is the solution:

'''
# Node Class:
class Node:
    def _init_(self,val):
        self.data = val
        self.left = None
        self.right = None
        '''
res = -999999999
def maxPathSumUtil(root):
    global res
    if root is None:
        return 0
    
    if root.left is None and root.right is None:
        return root.data

    ls=maxPathSumUtil(root.left)
    rs=maxPathSumUtil(root.right)
    
    if root.left and root.right:
        res=max(res,ls+rs+root.data)
        return max(ls+root.data,rs+root.data) #Line: Problem
    if root.left is None:
        return rs+root.data
    else:
        return ls+root.data


def maxPathSum(root):
    global res
    res = -999999999
    maxPathSumUtil(root)
    return res

Can anyone tell me why do we use return max(ls+root.data,rs+root.data). And if we do use return max(ls+root.data,rs+root.data) for checking the maximum value then why do we use res=max(res,ls+rs+root.data) and not just res = max(ls+root.data,rs+root.data).

EDIT:

For example:

Let's take this tree for example:

             10
           /   \
         8      2
       /  \
     3     5

In this, after recursive calls, ls becomes 3 and rs becomes 5. res becomes ls+rs+root.data which is 3+5+8 = 16. Then return max(ls+root.data,rs+root.data) which is max(11,13) = 13. Now after this according to me the function should just return 13 but that does not happen. Even though return is not a recursive statement. How is the control flow of the code happening?

Upvotes: 1

Answers (3)

Arpan Banerjee

Reputation: 1016

From each node, you need to return Math.max(left,right)+root.data; And you need to calculate the max only if it is not a leaf node. At each step, you need to do the above two operations.

There are few edge cases to be handled as well. I have added the details in the inline comments of the code, along with if you remove those edge cases check, then for which test case it will fail. So if you do a dry run yourself it should be clear. Also recommend you to practice these questions before you attempt this.

Here is the solution-

class Node
{
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
} 

class Solution
{
    private Node setTree(Node root){
          Node temp = new Node(0);
          
          //if tree is left most
          if(root.right==null){
              root.right=temp;
          }
          else{    //if tree is right most
              root.left=temp;
          }
          
          return root;
    }
    
    int maxSum=Integer.MIN_VALUE;
     private int getMaxSum(Node root){
        if(root==null) return 0;

        int left=getMaxSum(root.left);
        int right=getMaxSum(root.right);
        
        // [1 8 6 -7 -10 -9], if one of the child is null and other is leaf, we can t return 0 from the null leaf
        if(root.left==null && root.right!=null)
            left=Integer.MIN_VALUE;
        if(root.right==null && root.left!=null)
            right=Integer.MIN_VALUE;

        // difference from leetcoe max path sum is here, we cannot include the root itself even if it has a bigger value
        // since we have to return the sum till leaf from any node, so we need to carry the sum Max(left,right) from leaf
        // and add root to it, even if it reduces the sum
        int temp=Math.max(left,right)+root.data;
        
        // only calculate the max if its not the leaf node
        // [-9,6,10] ans= -13 and not 6
        if(root.left!=null && root.right!=null){
            maxSum=Math.max(maxSum,(left+right+root.data));
        }
        return temp;

    }
    int maxPathSum(Node root)
    { 
        // code here
        if(root.left==null || root.right==null){
            root=setTree(root);
        }
        getMaxSum(root);
        return maxSum;
    } 
}
/*
Some test cases to try out

        //do this only when both left and right are not null
        /*            2
                4           1
            7       10
        n       -3
        
        */ 
        // output -18
        // this also solves this problem, max sum already has a
        // bigger value for non leaf nodes summation
        
        /*      -10
            -1          0
        3
        */ //output -8
*/

Upvotes: 0

another_CS_guy

Reputation: 682

At each node, we have to check whether that node's left and right child resulted in max path. But when we return, we need to return either the left or right path depending upon whichever is max. Let's take this tree for example:

In this, after recursive calls, ls becomes 3 and rs becomes 5. res becomes ls+rs+root.data which is 3+5+8 = 16. So res(result) will be updated to 16, and return will be max(11,13) which is 13. Now this 13 value will be used by node 10 as ls(left value).

Upvotes: 0

trincot

Reputation: 350272

There are two things that are measured in parallel during execution:

ls+rs+root.data is the max path in the tree rooted by root, between two of the leaves below it. So it is (the value) of a leaf-to-leaf path
The function return value is the maximum path from root to any of the leaves below it. So it is (the value) of a root-to-leaf path

These are two different concepts and should not be mixed up.

Both ls and rs are function return values: ls represents the maximum path from root.left to a leaf. And in the same way rs represents the maximum path from root.right to a leaf.

ls+rs+root.data on the other hand, represents a path from leaf to leaf passing through root.

res should be updated if that latter expression is greater than res, hence the max().

But the function's return value should not represent a leaf-to-leaf path, but a root-to-leaf path. So that is why we have:

return max(ls+root.data,rs+root.data)

This tells the caller what the maximum root-to-leaf path is, not what the maximum leaf-to-leaf path is. The latter is used for determining res, not the function's return value.

I hope this clarifies the distinction between these two concepts and the roles they play in the algorithm.

The example

You presented this tree as example:

Indeed, when the function is called for the node 8, it:

sets res to 16 (the max path between two leaves below the node)
returns 13 (the max path from the node to one of its leaves)

You then ask:

Now after this according to me the function should just return 13 but that does not happen.

But it does happen like that. You should however not forget that this is the return value of maxPathSumUtil, not of maxPathSum. Also, this is not the top-level call of maxPathSumUtil. The value 13 is returned to another execution context of maxPathSumUtil, where root is the node 10. Then -- after another recursive call is made (with root equal to node 2), this top-level execution of the function maxPathSumUtil will:

set res to 25 (the max path between two leaves below the node 10)
return 23 (the max path from the node 10 to one of its leaves)

This toplevel call was made from within maxPathSum, which ignores the value returned by maxPathSumUntil. It only takes the value of res (25), and returns that:

maxPathSumUtil(root)  # notice that return value is ignored.
return res

Upvotes: 2

Maximum Path Sum between 2 Leaf Nodes(GeeksForGeeks)

Answers (3)

The example

Related Questions