✅ Easy to Understand | Recursion with Memorization | DP | Detailed Video Explanation🔥
IntuitionThe problem is a variation of the House Robber problem but applied to a binary tree. Since we cannot rob two directly linked houses (nodes), we must ma
# Intuition
The problem is a variation of the House Robber problem but applied to a binary tree. Since we cannot rob two directly linked houses (nodes), we must make an optimal choice at each node to maximize the robbed amount. The key observation is that for each node, we have two choices: either rob it and skip its children or skip it and consider robbing its children.

# Approach
We use a recursive approach with memoization to avoid redundant computations. 
1. Define a recursive function that takes a node and a boolean flag (`probbed`) indicating whether the parent node was robbed.
2. If the node is null, return 0 (base case).
3. Use a HashMap (`dp`) to store results to prevent recomputation.
4. If the current node is not robbed, we can include its value and call the function on its grandchildren.
5. If we skip the current node, we call the function on its immediate children.
6. The result for each node is the maximum of these two options.

# Complexity
- Time complexity:
  - Since we process each node once and use memoization, the time complexity is $$O(n)$$ where $$n$$ is the number of nodes in the tree.

- Space complexity:
  - The recursive call stack takes $$O(h)$$ space, where $$h$$ is the height of the tree. In the worst case (skewed tree), $$h = O(n)$$. The HashMap also takes $$O(n)$$ space for memoization. Therefore, the overall space complexity is $$O(n)$$.

# Code
```java []
class Solution {
    // HashMap to store computed results for each TreeNode to avoid recomputation (memoization)
    Map<TreeNode, Integer[]> dp;

    public int rob(TreeNode root) {
        dp = new HashMap(); // Initialize the memoization map
        return sol(root, false);  // Start the recursive function with root and 'false' (not robbed)
    }

    // Recursive function to determine the maximum money that can be robbed
    private int sol(TreeNode root, boolean probbed){
        if(root == null) // Base case: if the node is null, return 0
            return 0;
        
        // Store computed values for both states (robbed or not) to optimize recursion
        dp.putIfAbsent(root, new Integer[2]);
        if(dp.get(root)[probbed ? 1 : 0] != null) // If already computed, return cached result
            return dp.get(root)[probbed ? 1 : 0];

        int one = 0;
        // Case 1: If the current node is NOT robbed in the previous step, we can rob it
        if(!probbed){
            one = root.val + sol(root.left, true) + sol(root.right, true);
        }
        
        // Case 2: Skip robbing the current node and explore the next level of children
        int two = sol(root.left, false) + sol(root.right, false);
        
        // Store the maximum value from both choices in the memoization map and return it
        return dp.get(root)[probbed ? 1 : 0] = Math.max(one, two);
    }
}

```

https://youtu.be/xZYVvph1I-I
['Dynamic Programming', 'Tree', 'Depth-First Search', 'Binary Tree', 'Java']