Max Sum Path in Binary Tree | Dynamic Programming | Trees | Solution | C++ | Java

 

Problem Description:

Given a binary tree T, find the maximum path sum.

The path may start and end at any node in the tree.

Input Format:

The first and the only argument contains a pointer to the root of T, A.

Output Format:

Return an integer representing the maximum sum path.

Constraints:

1 <= Number of Nodes <= 7e4
-1000 <= Value of Node in T <= 1000

Example :

Input 1:

       1
      / \
     2   3

Output 1:
     6

Explanation 1:
    The path with maximum sum is: 2 -> 1 -> 3

Input 2:
    
       -10
       /  \
     -20  -30

Output 2:
    -10

Explanation 2
    The path with maximum sum is: -10

Approach:

For each node there can be four ways that the max path goes through the node:
1. Node only
2. Max path through Left Child + Node
3. Max path through Right Child + Node
4. Max path through Left Child + Node + Max path through Right Child

The idea is to keep track of four paths and pick up the max one in the end. An important thing to note is, the root of every subtree need to return maximum path sum such that at most one child of root is involved. This is needed for the parent function call. In below code, this sum is stored in ‘max_single’ and returned by the recursive function.

Below is the implementation of the above approach:

Problem Solution in C++ Programming Language:

code:

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

int  help(TreeNode* A,int &res)

{

    if(A==NULL) return 0;

    

    int l=help(A->left,res);

    int r=help(A->right,res);

    

    int m1= max(max(l,r)+A->val,A->val);

    int m2=max(m1,l+r+A->val);

    res=max(res,m2);

    

    return m1;

}

 

int Solution::maxPathSum(TreeNode* A) 

{

    int res=INT_MIN;

    int k=help(A,res);

    return res;

}

Problem Solution in Java Programming Language:

code:

/**

 * Definition for binary tree

 * class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

    

public class Solution {

    public int maxPathSum(TreeNode a) {

         Res res = new Res();

        res.val = Integer.MIN_VALUE;

 

        findMaxUtil(a, res);

        return res.val;

    }

    public class Res {

    public int val;

}

    

  

    int findMaxUtil(TreeNode node, Res res)

    {

 

        

        if (node == null)

            return 0;

        int l = findMaxUtil(node.left, res);

        int r = findMaxUtil(node.right, res);

 

       

        int max_single = Math.max(Math.max(l, r) + node.val,

                                  node.val);

 

        int max_top = Math.max(max_single, l + r + node.val);

 

        

        res.val = Math.max(res.val, max_top);

 

        return max_single;

    }

        

    

}

Thank you for reading.

For any questions, feedback and query comment below.

Keep coding!.

Open to suggestions please comment below:))