Problem Statement:
You are given an binary tree, you need to return the sum of the nodes such that no two nodes are adjecent.
It means, if we select a node, then we should not consider its children nodes in the solution.
You have to consider their grand children nodes.
Example
In the above example, the nodes present in green are choosen for the answer.
ALl the 3 nodes are not adjacent to each other.
Solution
The solution is very simple.
We use recursion to solve this problem.
For every node, we have an option to choose the node or not to choose the node.
So we will take 2 variables, the first variable will hold the max sum value if we choose the node.
Second variable will hold the amx sum if we do not choose the variable.
Solution in C++
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <list>
using namespace std;
class Node
{
public:
int data;
Node* left, *right;
Node(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
pair<int, int> max_sum_util(Node *root)
{
if (root==NULL)
{
pair<int, int> sum(0, 0);
return sum;
}
pair<int, int> sum1 = max_sum_util(root->left);
pair<int, int> sum2 = max_sum_util(root->right);
pair<int, int> sum;
// This node is included then Left and right children are not included
sum.first = sum1.second + sum2.second + root->data;
// This node is excluded then Either left or right child is included
sum.second = max(sum1.first, sum1.second) +
max(sum2.first, sum2.second);
return sum;
}
int get_max_sum(Node *root)
{
pair<int, int> res = max_sum_util(root);
return max(res.first, res.second);
}
int main()
{
Node *root= new Node(10);
root->left= new Node(1);
root->left->left= new Node(2);
root->left->left->left= new Node(1);
root->left->right= new Node(3);
root->left->right->left= new Node(4);
root->left->right->right= new Node(5);
cout <<"The max sum is = " <<get_max_sum(root);
return 0;
}
Output:
The max sum is = 21