✅ [C++/Python] Simple Solutions w/ Explanation | Optimization from Brute-Force to DP to Optimized DP
We are given a binary tree consisting of houses. We need to find maximum loot that we can get without robbing two directly linked houses\n\n---\n\n \u274C Solut
We are given a binary tree consisting of houses. We need to find maximum loot that we can get without robbing two directly linked houses\n\n---\n\n \u274C ***Solution - I (Brute-Force)***\n\nLet\'s try to solve this starting with brute-force.\n\n* At each house/node of the tree, we have the choice to either rob it or not to rob it\n* If we rob the current node, we cannot rob the left or right child of the current node\n* If we dont rob the current node, we can move to the left and right nodes and rob them\n* We choose the option which yields us the maximum loot\n\nWe can implement this in two ways- \n1. In 1st implementation below, I have used a boolean `canRob` variable denoting whether we can rob the current node or not. Each time we move to child nodes with `canRob` parameter set to true or false depending on whether the current node was robbed or not.\n2. In the 2nd implementation, we never move to directly linked nodes when we rob the current node. So we can either not rob the current node, or we can rob it and move to both child nodes of `root -> left` and `root -> right` if they exists.\n\nI found 1st version a bit simpler but the 2nd version will be better for optimization into `dp`.\n\n### **C++**\n> *1st Implementation*\n```cpp\nclass Solution {\npublic:\n    int rob(TreeNode* root, bool canRob = true) {\n        if(!root) return 0;\n        int dontRob = rob(root -> left, true) + rob(root -> right, true);\n        int robRoot = canRob ? root -> val + rob(root -> left, false) + rob(root -> right, false) : -1;\n        return max(dontRob, robRoot);\n    }\n};\n```\n\n> *2nd Implementation*\n```cpp\nclass Solution {\npublic:\n    int rob(TreeNode* root) {\n        if(!root) return 0;\n        int dontRob = rob(root -> left) + rob(root -> right), robRoot = root -> val;\n        if(root -> left) robRoot += rob(root -> left -> left) + rob(root -> left -> right);\n        if(root -> right) robRoot += rob(root -> right -> left) + rob(root -> right -> right);\n        return max(dontRob, robRoot);\n    }\n};\n```\n\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> <hr> \n\n### **Python**\n> *1st Implmentation*\n```python\nclass Solution:\n    def rob(self, root, canRob = True):\n        if not root: return 0\n        dont_rob = self.rob(root.left, True) + self.rob(root.right, True)\n        rob_root = root.val + self.rob(root.left, False) + self.rob(root.right, False) if canRob else -1\n        return max(dont_rob, rob_root)\n```\n\n> *2nd Implemtation*\n```python\nclass Solution:\n    def rob(self, root):\n        if not root: return 0\n        dont_rob, rob_root = self.rob(root.left) + self.rob(root.right), root.val\n        if root.left:   rob_root += self.rob(root.left.left)  + self.rob(root.left.right)\n        if root.right:  rob_root += self.rob(root.right.left) + self.rob(root.right.right)\n        return max(dont_rob, rob_root)\n```\n\n***Time Complexity :*** <code>O(2<sup>N</sup>)</code>, where `N` is the number of nodes in the tree. \n***Space Complexity :*** `O(H)`, where `H` is the height of the tree. `H` is the max recursion depth & thus `O(H)` space is required by recursive stack. It is `O(N)` in case of skewed tree and `O(logN)` in case of balanced binary tree.\n\n\n---\n\n \u2714\uFE0F ***Solution - II (Dynamic Programming)***\n\nDrawing out the recursion tree, we can see that there are multiple repeated computations taking place. But call to `rob()` with same parameters should always give us the same result which is maximum possible loot that we can get starting from that node. So, instead of doing repeated computations over and over again, we can simply save the result for a given state of function and directly return the same result when repeated call is made. \n\nHere, for the 1st case, we use a `dp` hashmap where `dp[node][canRob]` denotes the maximum possible loot that we can get starting from `node` in the tree & `canRob` denotes whether it can be robbed or not. Note that in this case we needed to save the complete state of function into `dp` which includes `canRob` parameter as well.\nSimilarly, for 2nd case, we use `dp` hashmap where `dp[node]` denotes the maximum possible loot that we can get starting from `node` in the tree.\n\n### **C++**\n> *1st Implementation*\n```cpp\nclass Solution {\npublic:\n    unordered_map<TreeNode*, vector<int>> dp;\n    int rob(TreeNode* root, bool canRob = true) {\n        if(!root) return 0;\n        if(dp.count(root) && dp[root][canRob] != -1) return dp[root][canRob];\n        dp[root] = {-1,-1};\n        int dontRob = rob(root -> left, true) + rob(root -> right, true);\n        int robRoot = canRob ? root -> val + rob(root -> left, false) + rob(root -> right, false) : -1;\n        return dp[root][canRob] = max(dontRob, robRoot);\n    }\n};\n```\n\n> *2nd Implementation*\n```cpp\nclass Solution {\npublic:\n    unordered_map<TreeNode*, int> dp;\n    int rob(TreeNode* root) {\n        if(!root) return 0;\n        if(dp.count(root)) return dp[root];\n        int dontRob = rob(root -> left) + rob(root -> right), robRoot = root -> val;\n        if(root -> left) robRoot += rob(root -> left -> left) + rob(root -> left -> right);\n        if(root -> right) robRoot += rob(root -> right -> left) + rob(root -> right -> right);\n        return dp[root] = max(dontRob, robRoot);\n    }\n};\n```\n\n### **Python**\n> *1st Implementation*\n```python\nclass Solution:\n    @cache\n    def rob(self, root, canRob = True):\n        if not root: return 0\n        dont_rob = self.rob(root.left, True) + self.rob(root.right, True)\n        rob_root = root.val + self.rob(root.left, False) + self.rob(root.right, False) if canRob else -1\n        return max(dont_rob, rob_root)\n```\n\n> *2nd Implemtation*\n```python\nclass Solution:\n    @cache\n    def rob(self, root):\n        if not root: return 0\n        dont_rob, rob_root = self.rob(root.left) + self.rob(root.right), root.val\n        if root.left:   rob_root += self.rob(root.left.left)  + self.rob(root.left.right)\n        if root.right:  rob_root += self.rob(root.right.left) + self.rob(root.right.right)\n        return max(dont_rob, rob_root)\n```\n\n***Time Complexity :*** <code>O(N)</code>, we calculate `dp[node]` for each of `N` nodes in the tree only once.\n***Space Complexity :*** `O(N)`, required for maintaining `dp`\n\n---\n\n \u2714\uFE0F ***Solution - III (Space-Optimized Dynamic Programming)***\n\nIn the above solutions, we recursed for both cases when current node was robbed and current node wasn\'t robbed and depending on the result from both cases, we decided which one to choose. This led to separate dfs calls with multiple states, one with current node\'s state as being robbed and other one with the state being not robbed. This required us memoize the results to avoid repeated calls to a node\'s state which was already calculated in one of earlier dfs call.\n\nGoing a slightly different route, instead of doing separate calls, we just make a single dfs call to left and right child nodes (without differentiating the state of current node) and return the results for both the cases of the child nodes being robbed and not robbed. We can then calculate the result for current node for -\n * state when **current node is robbed** which will be equal to current node\'s value + sum of result of child nodes not being robbed.\n * state when **current node is NOT robbed** which will be equal to sum of result of child nodes in their maximum loot state (i.e, for each child node, choose its state of either being robbed or not robbed, whichever gave maximum loot).\n\nTo summarize, this approach issues a single dfs call down till the leaf node and from there it propagates upwards the value of **1.** maximum loot when child node is not robbed and, **2.** maximum loot when child node is robbed. This allows us to calculate result for both states of current node being robbed and not being robbed without the need of memoizing the results for child nodes.\n\n### **C++**\n```cpp\nclass Solution {\npublic:\n    int rob(TreeNode* root) {\n        auto ans = dfs(root);\n        return max(ans.first, ans.second);\n    }\n    pair<int, int> dfs(TreeNode* root) {\n        if(!root) return {0, 0};\n        auto [leftDontRob, leftRob]   = dfs(root -> left);\n        auto [rightDontRob, rightRob] = dfs(root -> right);\n        return {\n            max(leftDontRob, leftRob) + max(rightDontRob, rightRob),\n            root -> val + leftDontRob + rightDontRob\n        };\n    }\n};\n```\n\n### **Python**\n```python\nclass Solution:\n    def rob(self, root):\n        def dfs(root):\n            if not root: return (0, 0)\n            L, R = dfs(root.left), dfs(root.right)\n            return (max(L) + max(R), root.val + L[0] + R[0])\n        return max(dfs(root))\n```\n\n***Time Complexity :*** <code>O(N)</code>\n***Space Complexity :*** `O(H)`, required for recursive stack\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---\n
[]