Binary Trees: Maximum Sum of nodes in Binary tree such that no two are adjacent

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

 

 

 

 

 

 

 

 

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *