GOOGLE INTERVIEW QUESTION | DP | INTUITIVE EXPLANATION !!
It is same as the question https://leetcode.com/problems/house-robber/  but now we have to steal in a Binary Tree. At that question We have used our DP as maxim
It is same as the question https://leetcode.com/problems/house-robber/  but now we have to steal in a Binary Tree. At that question We have used our DP as maximum profit at ith index if we pick value at ith index or we do not pick the value at ith index.\n\nHere We have to use the same Dp state but we have to use it to Every Node in the tree. At Every Node we can store the maximum profit till that node if we rob the node or if we donot rob it.\n\nSo you have to store a pair at every Node  pair is like ** <max profit if we robNode ,  max profit if we doNotRob> \n**\n**Crux: If you are robbing the currNode you cant rob the childrens.\nif you choose to rob the currNode\nmaxProfit if we ROB currNode=currNodeVal+maxSumOfleftChild when we dont rob it +maxSumOfrightChild when we dont rob it.\nbecause you cant rob the childrens if you rob the currNode**\n\n**If you choose to not rob the currNode then \nmaxProfit if we  doNotROB currNode=maxFromLeftPair+maxFromRightPair\nbecause if you are not robbing the current node then you can make any choice from the childrens you can rob the childrens or you dont its your wish so you have to return max from left child pair and from right child pair and add them.**\n\n```\nclass Solution\n{\n    \npublic:\n    pair<int,int> topDownDp(TreeNode* root)\n    {\n        if(root==NULL) return {0,0};\n        \n        pair<int,int> fromLeft=topDownDp(root->left);\n        pair<int,int> fromRight=topDownDp(root->right);\n \n        \n        int robNode=root->val+fromLeft.second+fromRight.second;\n        int doNotRob=max(fromLeft.first,fromLeft.second)+max(fromRight.first,fromRight.second);\n        \n        return {robNode,doNotRob};\n    }\n\n    int rob(TreeNode* root) \n    {\n    pair<int,int> choices=topDownDp(root);\n    return max(choices.first,choices.second);    \n    }\n\n};
[]