Easy Intuitive Recursion Python
Each Node in the tree has two options:\n\n1. \tNot Contribute to the max sum (money) in which case we just call the recursive function for left and right child 
Each Node in the tree has **two** options:\n\n1. \t**Not Contribute** to the max sum (money) in which case we just call the recursive function for left and right child and add them.\n\n```\n"""\ncond1 = self.rob(root.left)+self.rob(root.right)\n"""\n```\n\n2. \t**Contribute** to the max sum in which case we cannot select the immediate two childs of the node (as per the question constraints direct links cannot be added). In this case we add **the contribution of the current node** and **call the function on the four grandchildren of that node** and add all the four grandchildren sum. \n```\n"""\ncond2 = root.val + (self.rob(root.left.left)+self.rob(root.left.right)+self.rob(root.right.left)+self.rob(root.right.right)\n"""\n```\n\nGet the max of above conditions will be the answer.\n```\n"""\nreturn max(cond1,cond2)\n"""\n```\n\n\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    \n    def rob(self, root: Optional[TreeNode]) -> int:\n        \n#         """\n#         Base Condtions\n#         """\n        if(not root):\n            return 0\n        elif(not root.left and not root.right):\n            return root.val\n        # """\n        # if only left child is present. cond2 will not contain grandchildren of right ones\n        # cond1 will be as simple as just calling on left node;; no adding with right node required.\n        # """\n        elif(not root.right):\n            cond1 = self.rob(root.left)\n            cond2 = root.val+self.rob(root.left.left)+self.rob(root.left.right)\n            max_money = max(cond1,cond2)\n        # """\n        # If only right child is present ; similar as above explaination\n        # """\n        elif(not root.left):\n            cond1 = self.rob(root.right)\n            cond2 = root.val+self.rob(root.right.left)+self.rob(root.right.right)\n            max_money = max(cond1,cond2)\n            \n        else:\n            \n            cond1 = self.rob(root.left)+self.rob(root.right)\n            cond2 = root.val + (self.rob(root.left.left)+self.rob(root.left.right)+self.rob(root.right.left)+self.rob(root.right.right))\n            max_money = max(cond1,cond2)\n        \n        return max_money\n```\n\n**Inorder to optimise** the above Solution simply **use a dictionary** to store the sum value of a node so that it is not calculated again in recursive calls:\n\nOptimised code : (Same as Above; just added a dictionary)\n\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    d = {}\n    def rob(self, root: Optional[TreeNode]) -> int:\n        \n#         """\n#         Base Condtions\n#         """\n        if(not root):\n            return 0\n        \n        elif(Solution.d.get(root) != None):\n            return Solution.d[root]\n        \n        elif(not root.left and not root.right):\n            return root.val\n        # """\n        # if only left child is present. cond2 will not contain grandchildren of right ones\n        # cond1 will be as simple as just calling on left node;; no adding with right node required.\n        # """\n        elif(not root.right):\n            cond1 = self.rob(root.left)\n            cond2 = root.val+self.rob(root.left.left)+self.rob(root.left.right)\n            max_money = max(cond1,cond2)\n        # """\n        # If only right child is present ; similar as above explaination\n        # """\n        elif(not root.left):\n            cond1 = self.rob(root.right)\n            cond2 = root.val+self.rob(root.right.left)+self.rob(root.right.right)\n            max_money = max(cond1,cond2)\n            \n        else:\n            \n            cond1 = self.rob(root.left)+self.rob(root.right)\n            cond2 = root.val + (self.rob(root.left.left)+self.rob(root.left.right)+self.rob(root.right.left)+self.rob(root.right.right))\n            max_money = max(cond1,cond2)\n            \n        Solution.d[root] = max_money\n        \n        return max_money\n```
['Recursion', 'Binary Tree', 'Python']