Binary Tree Maximum Path Sum
You are given a binary tree with ‘N’ nodes.

Your task is to find the “Maximum Path Sum” for any path.

Note :

1. A ‘path’ is a sequence of adjacent pair nodes with an edge between them in the binary tree. 2. The ‘path’ doesn’t need to pass through the root. 3. The ‘path sum’ is the sum of the node’s data in that path.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases to be run. The first line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place. For example, the input for the tree is depicted in the below image.

For example, the input for the tree depicted in the above image would be : 1 2 3 4 -1 5 6 -1 -1 -1 -1 -1 -1

Explanation :

Level 1 : The root node of the tree is 1 Level 2 : Left child of 1 = 2 Right child of 1 = 3 Level 3 : Left child of 2 = 4 Right child of 2 = null (-1) Left child of 3 = 5 Right child of 3 = 6 Level 4 : Left child of 4 = null (-1) Right child of 4 = null (-1) Left child of 5 = null (-1) Right child of 5 = null (-1) Left child of 6 = null (-1) Right child of 6 = null (-1)

Note :

The above format was just to provide clarity on how the input is formed for a given tree. The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as: 1 2 3 4 -1 5 6 -1 -1 -1 -1 -1 -1

Output Format :

For each test case, print an integer denoting the maximum path sum. The output of each test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Binary Tree Maximum Path Sum

You are given a binary tree with ‘N’ nodes.

Your task is to find the “Maximum Path Sum” for any path.

Note :

1. A ‘path’ is a sequence of adjacent pair nodes with an edge between them in the binary tree.
2. The ‘path’ doesn’t need to pass through the root.
3. The ‘path sum’ is the sum of the node’s data in that path.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases to be run.

The first line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

For example, the input for the tree is depicted in the below image.

altImage

For example, the input for the tree depicted in the above image would be :

1
2 3
4 -1 5 6
-1 -1 -1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 =  6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = null (-1)
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
1 2 3 4 -1 5 6 -1 -1 -1 -1 -1 -1

Output Format :

For each test case, print an integer denoting the maximum path sum. 

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 2000
-5000 <= data <= 5000 and data != ‘-1’ (because -1  is used to mark the null nodes).

Where ‘N’ is the total number of nodes in the given binary tree, and ‘data’ is the value of the node of the binary tree.

Time Limit : 1sec

Accepted Answer

Recursive Approach

The idea here is to use the recursion. For each node, We can calculate the maximum path sum by keeping track of the following paths:

Max path sum starting from Left child + Max Path sum starting from Right child + Node’s value.
Max path sum starting from Left child + Node’s value
Max path sum starting from Right child + Node’s value
Node’s value

We then pick the maximum one among them. The root of every subtree will be going to return the maximum sum path having 0 or 1 child of the same.

Steps:

Declare a variable named ans to store the final answer.
Initialize it with INT_MIN.
Call the function find and pass root, a sum that is initially 0, and ans.
Return ans.

int find(root, sum, ans):

If the root is NULL, then return 0.
Call find again with the left of the root, and store its result into the variable leftSum.
Again call the find function, but this time, pass the root’s right, ans store its result into the variable rightSum.
Then try all four possible combinations:
- Update ans with max(ans, (leftSum + rightSum + root.data)).
- Update ans with max(ans, (leftSum + root.data)).
- Update ans with max(ans, (rightSum + root.data)).
- Update ans with max(ans, root.data).
Return the max(root.data, max(leftSum, rightSum) + root.data).

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the Binary Tree.

In the worst case, the recursive stack can increase up to a size of N. Hence, the space complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the Binary Tree.

We are using the recursive function and visiting each node exactly once. Hence, the overall time complexity will be O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of Nodes in the binary tree.

*/



public class Solution 

{   

    public static int ans;



    public static int find(TreeNode root, int sum)

    {

        // If root is NULL.

        if (root == null)

        {

            return 0;

        }

    

        // Call the left child.

        int leftSum = find(root.left, sum);

        

        // Call the right child.

        int rightSum = find(root.right, sum);

    

        // Update ans by checking all possible combinations.

        ans = Math.max(ans, leftSum + rightSum + root.val);

        ans = Math.max(ans, leftSum + root.val);

        ans = Math.max(ans, rightSum + root.val);

        ans = Math.max(ans, root.val);

    

        // Finally return the maximum of the following.

        return Math.max(root.val, Math.max(leftSum, rightSum) + root.val);

    }



    public static int maxPathSum(TreeNode root) 

    {

	    // Declare a variable to store the final answer.

	    ans = Integer.MIN_VALUE;

	    

        // Call the function find.

	    find(root, 0);



	    return ans;

	}

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of Nodes in the binary tree.

'''



def find(root, sum, ans):



	# If root is None.

	if (root == None):

		return 0,ans



	# Call the left child.

	leftSum, ans = find(root.left, sum, ans)

	

    # Call the right child.

	rightSum, ans = find(root.right, sum, ans)



	# Update ans by checking all possible combinations.

	ans = max(ans, leftSum + rightSum + root.val)

	ans = max(ans, leftSum + root.val)

	ans = max(ans, rightSum + root.val)

	ans = max(ans, root.val)



	# Finally return the maximum of the following.

	return max(root.val, max(leftSum, rightSum) + root.val),ans



def maxPathSum(root):



	# Declare a variable to store the final answer.

	ans = -1000000007

	

    # Call the function find.

	temp, ans = find(root, 0, ans)



	return ans

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where N is the number of Nodes in the binary tree.

*/



int find(TreeNode* root, int sum, int *ans)

{

	// If root is NULL.

	if (root == NULL)

	{

		return 0;

	}



	// Call the left child.

	int leftSum = find(root->left, sum, ans);

	

    // Call the right child.

	int rightSum = find(root->right, sum, ans);



	// Update ans by checking all possible combinations.

	*ans = max(*ans, leftSum + rightSum + root->val);

	*ans = max(*ans, leftSum + root->val);

	*ans = max(*ans, rightSum + root->val);

	*ans = max(*ans, root->val);



	// Finally return the maximum of the following.

	return max(root->val, max(leftSum, rightSum) + root->val);

}



int maxPathSum(TreeNode* root)

{

	// Declare a variable to store the final answer.

	int ans = INT_MIN;

	

    // Call the function find.

	find(root, 0, &ans);



	return ans;

}

You are given a binary tree with ‘N’ nodes.

Your task is to find the “Maximum Path Sum” for any path.

Note :

Input Format :

Explanation :

Note :

Output Format :

Note :

Constraints :

Top InterviewBit Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern