### C++program to maximum sum of nodes in binary tree such that no two are adjacent

`/* *In this problem we have to select the node of the binary tree such that there   sum is maximum but no two node should be connected to each other. *The simple approach is that add the value of the top node and its grandchildren  recursively till we can't further add it. *After that do the same process for the every child of the above top node. *To stop re-computation the subproblem which has been solved we use map to   memorizing the sum of the subtree. 						11					       /  \					      12   13					     /    /  \					    11   14   15				The Maximums sum is 11+11+14+15=52*/#include <bits/stdc++.h> using namespace std; struct node { 	int data; 	struct node *left, *right; }; //create new nodestruct node* newNode(int data) { 	struct node *temp = new struct node; 	temp->data = data; 	temp->left = temp->right = NULL; 	return temp; } // Declaration of methods int getSumOfChildren(node* node); int getMaxSum(node* node); int getMaxSumRoot(node* node, map<struct node*, int>& mp); // function to give the maximum sum possible from subtrees rooted // at grandChildrens of node 'node'  int getSumOfChildren(node* node, map<struct node*, int>& mp) { 	int sum = 0; 	// call for children of left child only if it is not NULL 	if (node->left) 		sum += getMaxSumRoot(node->left->left, mp) + 			getMaxSumRoot(node->left->right, mp); 	// call for children of right child only if it is not NULL 	if (node->right) 		sum += getMaxSumRoot(node->right->left, mp) + 			getMaxSumRoot(node->right->right, mp); 	return sum; } // function get the maximum sum rooted at node 'node' int getMaxSumRoot(node* node, map<struct node*, int>& mp) { 	if (node == NULL) 		return 0; 	// If node is already processed then return calculated 	// value from map 	if (mp.find(node) != mp.end()) 		return mp[node]; 	// take current node value and call for all grand children 	int incl = node->data + getSumOfChildren(node, mp); 	// don't take current node value and call for all children 	int excl = getMaxSumRoot(node->left, mp) + 			getMaxSumRoot(node->right, mp); 	// choose maximum from both above calls and store that in map 	mp[node] = max(incl, excl); 	return mp[node]; } // function to get the maximum sum from subset of nodes // of binary tree under given constraints int getMaxSum(node* node) { 	if (node == NULL) 		return 0; 	map<struct node*, int> mp; 	return getMaxSumRoot(node, mp); } int main() { 	node* root = newNode(11); 	root->left = newNode(12); 	root->right = newNode(13); 	root->right->left = newNode(14); 	root->right->right = newNode(15); 	root->left->left = newNode(11); 	cout<<getMaxSum(root)<<endl; 	return 0; } /*	OUTPUT:-		52*/`