Maximum Sum of nodes in a binary tree such that no two nodes are adjacent
You have been given a binary tree with an integer value associated to each node. You are supposed to choose a subset of these nodes such that the sum of these chosen nodes is maximum. Keep in mind that no two of the chosen nodes must be adjacent to each other.

Note :

Two nodes are said to be adjacent to each other if they are directly connected to each other. This means that if a node is taken as part of the sum, then none of its children can be considered for the same and vice versa.

For example :

For the given binary tree

Nodes used in consideration for maximum sum such that no two of them are adjacent are highlighted. Maximum sum of nodes = 1 + 1 + 1 + 4 + 5 = 12.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows. 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 depicted in the below image would be :

Input Format : 1 2 3 4 -1 5 6 -1 7 -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 = 7 Left child of 5 = null (-1) Right child of 5 = null (-1) Left child of 6 = null (-1) Right child of 6 = null (-1) Level 5 : Left child of 7 = null (-1) Right child of 7 = null (-1) The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on. The input ends when all nodes at the last level are 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 7 -1 -1 -1 -1 -1 -1

Output Format :

For each test case, print the maximum sum of nodes keeping the above constraints in mind. Print the output of each test case in a separate line.

Note :

You do not need to print anything; it has already been taken care of. You just need to return the maximum sum of nodes.

Constraints :

1

Question

Maximum Sum of nodes in a binary tree such that no two nodes are adjacent

You have been given a binary tree with an integer value associated to each node. You are supposed to choose a subset of these nodes such that the sum of these chosen nodes is maximum. Keep in mind that no two of the chosen nodes must be adjacent to each other.

Note :

Two nodes are said to be adjacent to each other if they are directly connected to each other. This means that if a node is taken as part of the sum, then none of its children can be considered for the same and vice versa.

For example :

For the given binary tree

Example

Nodes used in consideration for maximum sum such that no two of them are adjacent are highlighted. Maximum sum of nodes = 1 + 1 + 1 + 4 + 5 = 12.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.

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 depicted in the below image would be :

Example

Input Format :   
1
2 3
4 -1 5 6
-1 7 -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 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

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

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are 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 7 -1 -1 -1 -1 -1 -1

Output Format :

For each test case, print the maximum sum of nodes keeping the above constraints in mind.

Print the output of each test case in a separate line.

Note :

You do not need to print anything; it has already been taken care of. You just need to return the maximum sum of nodes.

Constraints :

1 <= T <= 100
0 <= N <= 3000
1 <= data <= 10^4

 Where ‘T’ is the number of test cases, and ‘N’ is the total number of nodes in the binary tree, and “data” is the value of the binary tree node.

Time Limit : 1 sec

Accepted Answer

Using Memoization

Keeping in mind the fact that both node and its children can not be considered for the maximum sum at the same time, we know that if we take a node into our sum, then we will directly call recursively for its grandchildren, OR if we don't take the node into our consideration, we will call for its child nodes and finally consider the maximum sum from both these results.

Considering the above idea, we now think about making a working approach to this problem. The drawbacks of the above idea are that it can lead to solving the same subproblems multiple times.

For example: Consider this binary tree:

Now, here when we choose the root node ‘1’, it will call its grandchild nodes ‘4’ and ‘5’. Similarly when we move to child node ‘3’ and do not select it, then again the nodes ‘4’ and ‘5’ will be called child nodes of ‘3’. This leads to processing nodes ‘4’ and ‘5’ more than once.

In order to stop solving these nodes more than one time, we will memorize the result at each node.

In order to solve this problem, we will use an unordered_map for memoizing the result which stores the result of the complete subtree rooted at a node in the unordered_map, so that if we call the same node again, instead of calculating the value again, we can directly return the value stored in the map.

Algorithm:

Create a function that returns the maximum sum of nodes from the subset of nodes of the Binary tree under certain given conditions. Create an unordered_map that stores the result of subtree sum.
Create a function that returns maximum sum rooted at a certain node ‘node’
- If the node = 0, simply return 0
- Check if node is already processed:
  - If yes, return the calculated value from the map
  - If no, move forward
- Take the current node value and recursively call for all its grandchild nodes and store the value in a variable say “node_included”
- Now, don’t take the current node value and hence, recursively call for all its child nodes and store it in a separate variable say “node_not_included”
- Now, finally choose the maximum of “node_included” and “node_not_included” values and store it in the map.
- Return map.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of nodes in the given binary tree.

Since we are storing the results of each node in a map, the space complexity required for creating an unordered_map, makes the space complexity to be O(N).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of nodes in the given binary tree.

Since we are visiting each node exactly once, and at each function call, we are checking if the node is already processed or not, the overall time complexity is O(N).

C++ (g++ 5.4)

/*

    Time Complexity : O(N)

    Space Complexity : O(N)

	

    Where 'N' is the number of nodes in the given binary tree.

*/



#include



// Returns maximum sum from subset of nodes of binary tree under given constraints

int maximumSum(TreeNode *root, unordered_map *, int>& mp)

{

	if(root == NULL)

	{

        // If tree is empty 

		return 0;

	}

	

    if(root -> left == NULL && root -> right == NULL)

	{

        // If root does not have any child nodes

		return root -> data;

	}

	

    if(mp[root] != 0)

	{

        // return sum stored

		return mp[root];

	}



	int left_side = 0;

    int right_side = 0;

	

    if(root -> left != NULL )

	{

        // Calculate left subtree sum

		left_side = maximumSum(root -> left -> left , mp) + maximumSum(root -> left -> right, mp);

	}

	

    if(root -> right != NULL)

	{

        // Calculate right subtree sum

		right_side = maximumSum(root -> right -> left, mp) + maximumSum(root -> right -> right, mp);

	}



	// store both cases in different variables

	int x = left_side + right_side + root -> data;

	int y = maximumSum(root -> left, mp) + maximumSum(root -> right, mp);

    

	// return max of the two cases

	return mp[root] = max(x, y);

}



int maximumSumOfNodes(TreeNode *root)

{

    // Initialise a map to store the max sum

    unordered_map *, int> mp;

    

    int res = maximumSum(root, mp);

    return res;

}

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(N)

	

    Where 'N' is the number of nodes in the given binary tree.

'''



# Returns maximum sum from subset of nodes of binary tree under given constraints

def maximumSum(root,mp):



	if(root == None):



        # If tree is empty 

		return 0



	if(root.left == None and root.right == None):



        # If root does not have any child nodes

		return root.data



	if(root in mp):



        # return sum stored

		return mp[root]



	left_side = 0

	right_side = 0

	

	if(root.left != None):



        # Calculate left subtree sum

		left_side = maximumSum(root.left.left , mp) + maximumSum(root.left.right, mp)



	if(root.right != None):



        # Calculate right subtree sum

		right_side = maximumSum(root.right.left, mp) + maximumSum(root.right.right, mp)



	# store both cases in different variables

	x = left_side + right_side + root.data

	y = maximumSum(root.left, mp) + maximumSum(root.right, mp)

    

	# return max of the two cases

	mp[root] = max(x, y)

	return mp[root]





def maximumSumOfNodes(root):



    # Initialise a map to store the max sum

    mp = {}

    

    res = maximumSum(root, mp)

    return res

Java (SE 1.8)

/*

    Time Complexity : O(N)

    Space Complexity : O(N)

	

    Where 'N' is the number of nodes in the given binary tree.

*/



import java.util.HashMap;



public class Solution 

{

	// Returns maximum sum from subset of nodes of binary tree under given constraints

	private static int maximumSum(TreeNode root, HashMap, Integer> mp) 

    {

		if (root == null) 

        {

			// If tree is empty

			return 0;

		}

        

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

        {

			// If root does not have any child nodes

			return root.data;

		}

        

		if (mp.containsKey(root)) 

        {

			// Return the stored sum.

			return mp.get(root);

		}



		int left_side = 0;

        int right_side = 0;

		

        if (root.left != null) 

        {

			// Calculate left subtree sum.

			left_side = maximumSum(root.left.left, mp) + maximumSum(root.left.right, mp);

		}

        

		if (root.right != null) 

        {

			// Calculate right subtree sum.

			right_side = maximumSum(root.right.left, mp) + maximumSum(root.right.right, mp);

		}



		// Store both cases in different variables.

		int x = left_side + right_side + root.data;

		int y = maximumSum(root.left, mp) + maximumSum(root.right, mp);



		// Return maximum of the two cases.

		mp.put(root, Math.max(x, y));



		return Math.max(x, y);

	}



	public static int maximumSumOfNodes(TreeNode root) 

    {

		// Initialise a map to store the max sum

		HashMap, Integer> mp = new HashMap, Integer>();

		

        int res = maximumSum(root, mp);

		return res;

	}

}

Accepted Answer

Using Pair

The idea of this approach is to use a pair for each node. The first value of the pair will store the sum when the current node is included, meaning child nodes are not included. While the second value of the pair will store the sum when the current node is not included, meaning the child nodes are included. Finally, return the maximum of both first and second values.

Algorithm:

Create a pair that stores the values of the root node.
Create a function that returns a pair containing two values.
- One from including node.
- One from not including node.
For the first value: The node is included, meaning both the child nodes are not included.
For the second value: Do not include the node meaning the child nodes are included.
Return the maximum of both these values.

Space Complexity: O(1)Explanation:

O(1)

No extra space is required, hence the overall space complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of nodes in the given binary tree.

Since we are visiting each node only once and storing the sum in a pair, the overall time complexity is O(N).

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(1)

	

    Where 'N' is the number of nodes in the given binary tree.

'''



def maximumSum(root):



    max_sum = [0, 0]



	# If tree is empty

    if (root == None):



		# Both values of maximum sum of an empty tree will be 0

        return max_sum



	# Initialise pair to calculate sum from left subtree and right subtree

    left_sum = maximumSum(root.left)

    right_sum = maximumSum(root.right)



    # The current node is included meaning that left and right children are not included

    max_sum[0] = left_sum[1] + right_sum[1] + root.data 

    

    # The current node is not included meaning that either left or right children is included

    max_sum[1] = max(left_sum[0], left_sum[1]) + max(right_sum[0], right_sum[1])

 

    return max_sum





def maximumSumOfNodes(root):



	# Initialise a pair to store sum of nodes that calls the function

	res = maximumSum(root)



	# Return maximum of the first and second values of the pair

	return max(res[0], res[1])

C++ (g++ 5.4)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)

	

    Where 'N' is the number of nodes in the given binary tree.

*/



pair maximumSum(TreeNode *root)

{

    pair max_sum;



	// If tree is empty

    if (root == NULL)

    {

		// Both values of maximum sum of an empty tree will be 0

        max_sum.first = 0;

        max_sum.second = 0;

        return max_sum;

    }



	// Initialise pair to calculate sum from left subtree and right subtree

    pair left_sum = maximumSum(root -> left);

   pair right_sum = maximumSum(root -> right);



    // The current node is included meaning that left and right children are not included

    max_sum.first = left_sum.second + right_sum.second + root->data;

 

    // The current node is not included meaning that either left or right children is included

	max_sum.second = max(left_sum.first, left_sum.second) + max(right_sum.first, right_sum.second);

 

	return max_sum;

}



int maximumSumOfNodes(TreeNode *root)

{

	// Initialise a pair to store sum of nodes that calls the function

	pair res = maximumSum(root);



	// Return maximum of the first and second values of the pair

    return max(res.first, res.second);

}

Java (SE 1.8)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)

	

    Where 'N' is the number of nodes in the given binary tree.

*/



import java.util.ArrayList;



public class Solution 

{

	private static ArrayList maximumSum(TreeNode root) 

    {

		ArrayList max_sum = new ArrayList(2);



		// If tree is empty

		if (root == null) 

        {

			// Both values of maximum sum of an empty tree will be 0

			max_sum.add(0);

			max_sum.add(0);

			return max_sum;

		}



		// Initialise pair to calculate sum from left subtree and right subtree

		ArrayList left_sum = maximumSum(root.left);

		ArrayList right_sum = maximumSum(root.right);



		// The current node is included meaning that left and right children are not included

    	max_sum.add(left_sum.get(1) + right_sum.get(1) + root.data);



		// The current node is not included meaning that either left or right children is included

	 	max_sum.add(Math.max(left_sum.get(0), left_sum.get(1)) + Math.max(right_sum.get(0), right_sum.get(1)));



		return max_sum;

	}



	public static int maximumSumOfNodes(TreeNode root) 

    {

		// Initialise a pair to store sum of nodes that calls the function

		ArrayList res = maximumSum(root);



		// Return maximum of the first and second values of the pair

		return Math.max(res.get(0), res.get(1));

	}

}

You have been given a binary tree with an integer value associated to each node. You are supposed to choose a subset of these nodes such that the sum of these chosen nodes is maximum. Keep in mind that no two of the chosen nodes must be adjacent to each other.

Note :

For example :

Input Format :

Explanation :

Note :

Output Format :

Note :

Constraints :

Top Fidelity International Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern