Course4all
Join us on telegram
Home/dsa/Trees/House Robber III

House Robber III

Master this topic with zero to advance depth.

House Robber III

Tree robbery.

Medium
Approach 1

Level I: Brute Force Recursion

Intuition

Each node can either be robbed or not robbed. If we rob a node, we cannot rob its direct children. If we don't rob it, we can either rob its children or not.

Logic

rob(root) = max(root.val + rob(left.left) + rob(left.right) + rob(right.left) + rob(right.right), rob(left) + rob(right)).

⏱ O(2^N) (Exponential overlapping subproblems)💾 O(H)

Detailed Dry Run

At root: Option 1 (Rob 1 + grandchildren). Option 2 (Rob children 2 and 3). Max is 3.

java
public class Main {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int val = root.val;
        if (root.left != null) val += rob(root.left.left) + rob(root.left.right);
        if (root.right != null) val += rob(root.right.left) + rob(root.right.right);
        return Math.max(val, rob(root.left) + rob(root.right));
    }
}
Approach 2

Level II: Memoization

Intuition

We can store the result of rob(node) in a HashMap to avoid recomputing for the same node multiple times.

⏱ O(N)💾 O(N)

Detailed Dry Run

Store [Node Pointer] -> Max rob value.

java
public class Main {
    Map<TreeNode, Integer> memo = new HashMap<>();
    public int rob(TreeNode root) {
        if (root == null) return 0;
        if (memo.containsKey(root)) return memo.get(root);
        int val = root.val;
        if (root.left != null) val += rob(root.left.left) + rob(root.left.right);
        if (root.right != null) val += rob(root.right.left) + rob(root.right.right);
        int res = Math.max(val, rob(root.left) + rob(root.right));
        memo.put(root, res);
        return res;
    }
}
Approach 3

Level III: Optimal (Post-order DP Pair)

Intuition

Each node returns a pair: [max if robbed, max if NOT robbed].

  1. If we rob root, we must NOT rob its children: root.val + left[1] + right[1].
  2. If we DON'T rob root, we take the max of robbing or not robbing each child: max(left) + max(right).
⏱ O(N)💾 O(H)

Detailed Dry Run

Leaf returns [val, 0]. Parent returns [parentVal + 0, leafVal + 0].

java
public class Main {
    public int rob(TreeNode root) {
        int[] res = helper(root);
        return Math.max(res[0], res[1]);
    }
    private int[] helper(TreeNode root) {
        if (root == null) return new int[2];
        int[] left = helper(root.left);
        int[] right = helper(root.right);
        int rob = root.val + left[1] + right[1];
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{rob, notRob};
    }
}
← Previous QuestionConstruct Binary Tree from Preorder and Postorder
Next Question →Top K Frequent Elements