forked from imsushant12/GFG-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Maximum_sum_of_non-adjacent_nodes_of_BT.cpp
70 lines (58 loc) · 1.6 KB
/
Maximum_sum_of_non-adjacent_nodes_of_BT.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
Problem Statement:
-----------------
Given a binary tree with a value associated with each node, we need to choose a subset of these nodes such that the sum of chosen nodes is maximum
under a constraint that no two chosen node in the subset should be directly connected that is, if we have taken a node in our sum then we can’t take any of its children
in consideration and vice versa.
*/
// Link -->
// Code:
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
unordered_map <Node *, int> dp;
int findSum(Node *root)
{
if (root == NULL)
return 0;
if (dp[root])
return dp[root];
// Including the root of the tree then we have to skip
// its children and consider its grand-children.
int include = root->data;
if (root->left)
{
include += findSum(root->left->left);
include += findSum(root->left->right);
}
if (root->right)
{
include += findSum(root->right->left);
include += findSum(root->right->right);
}
// When we are excluding the root node, then we will consider children.
int exclude = findSum(root->left) + findSum(root->right);
dp[root] = max(include, exclude);
return dp[root];
}
int main()
{
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(1);
root->right->left = new Node(4);
root->right->right = new Node(5);
cout << "Maximum sum is : " << findSum(root);
return 0;
}