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














































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 node
struct 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
*/


Comments