Maximum sum of Non-adjacent Nodes

struct Node
{
    int data;
    Node* left;
    Node* right;
};
*/
/*
Logic :T.C(O(n)) and S.C O(n)
two case at every node:
case1: select current node,then select grand childrens and because all nodes are positive so add max_sum achieved
from all the grandchildren ie. incl means included

case2:don't select current node,so select it's child ie. excl means excluded
finally return the maximum of both.
used map for avoiding same recusion


*/

unordered_map<Node*,int> mp;
class Solution{
  public:
    //Function to return the maximum sum of non-adjacent nodes.
    int getMaxSum(Node *root){
        if(!root) return 0;
        if(mp[root]) return mp[root];

        int incl=root->data,excl=0;
        if(root->left){
            incl+=getMaxSum(root->left->left);
            incl+=getMaxSum(root->left->right);
        }
        if(root->right){
            incl+=getMaxSum(root->right->left);
            incl+=getMaxSum(root->right->right);
        }
        excl+=getMaxSum(root->left)+getMaxSum(root->right);
        mp[root]=max(incl,excl);
        return mp[root];
    }
};