Maximum sum of nodes in Binary tree such that no two are adjacent | C ++ program to find maximum sum from a subset of nodes of binary tree ; A binary tree node structure ; Utility function to create a new Binary Tree node ; Declaration of methods ; method returns maximum sum possible from subtrees rooted at grandChildrens of node ' node ' ; call for children of left child only if it is not NULL ; call for children of right child only if it is not NULL ; Utility method to return maximum sum rooted at node ' node ' ; If node is already processed then return calculated value from map ; take current node value and call for all grand children ; don 't take current node value and call for all children ; choose maximum from both above calls and store that in map ; Returns maximum sum from subset of nodes of binary tree under given constraints ; Driver code to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct node { int data ; struct node * left , * right ; } ; struct node * newNode ( int data ) { struct node * temp = new struct node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } int sumOfGrandChildren ( node * node ) ; int getMaxSum ( node * node ) ; int getMaxSumUtil ( node * node , map < struct node * , int > & mp ) ; int sumOfGrandChildren ( node * node , map < struct node * , int > & mp ) { int sum = 0 ; if ( node -> left ) sum += getMaxSumUtil ( node -> left -> left , mp ) + getMaxSumUtil ( node -> left -> right , mp ) ; if ( node -> right ) sum += getMaxSumUtil ( node -> right -> left , mp ) + getMaxSumUtil ( node -> right -> right , mp ) ; return sum ; } int getMaxSumUtil ( node * node , map < struct node * , int > & mp ) { if ( node == NULL ) return 0 ; if ( mp . find ( node ) != mp . end ( ) ) return mp [ node ] ; int incl = node -> data + sumOfGrandChildren ( node , mp ) ; int excl = getMaxSumUtil ( node -> left , mp ) + getMaxSumUtil ( node -> right , mp ) ; mp [ node ] = max ( incl , excl ) ; return mp [ node ] ; } int getMaxSum ( node * node ) { if ( node == NULL ) return 0 ; map < struct node * , int > mp ; return getMaxSumUtil ( node , mp ) ; } int main ( ) { node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> right -> left = newNode ( 4 ) ; root -> right -> right = newNode ( 5 ) ; root -> left -> left = newNode ( 1 ) ; cout << getMaxSum ( root ) << endl ; return 0 ; }