Find the maximum path sum between two leaves of a binary tree | GeeksforGeeks

Find the maximum path sum between two leaves of a binary tree | GeeksforGeeks
Given a binary tree in which each node element contains a number. Find the maximum possible sum from one leaf node to another.

The idea is to maintain two values in recursive calls
1) Maximum root to leaf path sum for the subtree rooted under current node.
2) The maximum path sum between leaves (desired output).

For every visited node X, we find the maximum root to leaf sum in left and right subtrees of X. We add the two values with X->data, and compare the sum with maximum path sum found so far.

    int maxPathSumUtil(Node node, Res res) {

  

        // Base cases

        if (node == null)

            return 0;

        if (node.left == null && node.right == null)

            return node.data;

  

        // Find maximum sum in left and right subtree. Also

        // find maximum root to leaf sums in left and right

        // subtrees and store them in ls and rs

        int ls = maxPathSumUtil(node.left, res);

        int rs = maxPathSumUtil(node.right, res);

  

        // If both left and right children exist

        if (node.left != null && node.right != null) {

  

            // Update result if needed

            res.val = Math.max(res.val, ls + rs + node.data);

  

            // Return maxium possible value for root being

            // on one side

            return Math.max(ls, rs) + node.data;

        }

  

        // If any of the two children is empty, return

        // root sum for root being on one side

        return (node.left == null) ? rs + node.data

                : ls + node.data;

    }

  

    // The main function which returns sum of the maximum

    // sum path between two leaves. This function mainly

    // uses maxPathSumUtil()

    int maxPathSum(Node node)

    {

        Res res = new Res();

        res.val = Integer.MIN_VALUE;

        maxPathSumUtil(root, res);

        return res.val;

    }




http://algorithms.tutorialhorizon.com/given-a-binary-tree-find-the-maximum-path-sum-between-any-two-leaves/

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

    public static int maxSoFar =0;
    public int maxPathSum(Node root){
        if(root!=null){
            int leftS = maxPathSum(root.left);
            int rightS = maxPathSum(root.right);
            int sumCurrent;
            if(leftS<0 && rightS<0){//??? it's not a leaf
                sumCurrent = root.data;
            }else{
                sumCurrent = Math.max(leftS+rightS+root.data , Math.max(leftS, rightS));
            }
//            sumCurrent = Math.max(leftS+rightS+root.data , Math.max(leftS, rightS));
            if(maxSoFar<sumCurrent){
                maxSoFar = sumCurrent;
            }
            return Math.max(leftS,rightS)+root.data;
        }
        else return 0;

    }
http://gohired.in/2015/05/maximum-path-sum-between-two-leaves/

A simple solution is to traverse the tree and do following for every traversed node X.

1) Find maximum sum from leaf to root in left subtree of X (we can use this post for this and next steps)

2) Find maximum sum from leaf to root in right subtree of X.

3) Add the above two calculated values and X->data and compare the sum with the maximum value obtained so far and update the maximum value.

4) Return the maximum value.

The time complexity of above solution is O(n²)

Read full article from Find the maximum path sum between two leaves of a binary tree | GeeksforGeeks