Dp on Binary Trees | Learn How to Tackle such Problems | 95% Faster
Approach:-\n The Thief cannot choose the two adjacent nodes right?\n Also, If we know the maximum amount the thief can stole for the child and grand child nodes
**Approach:-**\n* The Thief *cannot choose the two adjacent nodes* right?\n* Also, If we know the maximum amount the thief can stole for the child and grand child nodes of current node, we can answer the maximum amount for current node also...Guess Why? [Think for above condition].\n* Since, *If we choose current node into our answer*, we cannot take the child nodes of the current node right? Hence, **we\'d be looking for maximum answer we can get with grand child nodes**.\n* When *we don\'t choose current node into our answer*, **we would look for maximum answer for left as well as right child nodes**.\n* **dp[node v] = max(root->val + dp[left grand child of v] + dp[right grand child of v] , dp[left child of v] + dp[right child of v] )** is the dp relation.\n* Wait, How we would maintain an array in binary tree?, If you\'d notice we want only values for child nodes and grand child nodes right?\n* So, we would maintain a **pair<int,int>** for every node **{max ans child nodes, max ans for grand child nodes}** and recursively calculate answer for every node.\n\n```\nclass Solution {\npublic:\n    // TIME COMPLEXITY:- O(N)\n    // SPACE COMPLEXITY:- O(1) [neglecting the extra space due to recursion stack]\n    pair<int,int> findMax(TreeNode* root){\n        if(!root)\n            return {0,0};\n        pair<int,int> l = findMax(root->left); // {max ans for left child, max ans for left grand child}\n        pair<int,int> r = findMax(root->right); // {max ans for right child, max ans for right grand child}\n        return {max(root->val+l.second+r.second,l.first+r.first),l.first+r.first}; // either choose the current node or go with the grand child nodes\n    }\n    int rob(TreeNode* root) {\n        return findMax(root).first; // answer will be the max ans for current node\n    }\n};\n```\n\n**Don\'t forget to Upvote!**
[]