House Robber III

Difficulty: Medium Source: NeetCode

Problem

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root. Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night. Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1: Input: root = [3,2,3,null,3,null,1] Output: 7 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2: Input: root = [3,4,5,1,3,null,1] Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

Constraints:

• The number of nodes in the tree is in the range [1, 10^4]
• 0 <= Node.val <= 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• House Robber I/II — The base DP problem on arrays
• Post-order DFS — Computing answers bottom-up from leaves to root
• State Pairs — Returning two values from each DFS call (rob vs skip)

1. Naive Recursive with Memoization

Intuition

At each node, we have two choices: rob it (and skip both children) or skip it (and take the best from children). This creates overlapping subproblems — the same node’s subtree gets evaluated multiple times. Memoization fixes this.

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob_memo(root):
    memo = {}

    def dfs(node):
        if not node:
            return 0
        if node in memo:
            return memo[node]

        # Option 1: Rob this node → skip children, can rob grandchildren
        rob_this = node.val
        if node.left:
            rob_this += dfs(node.left.left) + dfs(node.left.right)
        if node.right:
            rob_this += dfs(node.right.left) + dfs(node.right.right)

        # Option 2: Skip this node → take best from each child
        skip_this = dfs(node.left) + dfs(node.right)

        memo[node] = max(rob_this, skip_this)
        return memo[node]

    return dfs(root)

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([3, 2, 3, None, 3, None, 1])
print(rob_memo(root1))  # 7

root2 = build_tree([3, 4, 5, 1, 3, None, 1])
print(rob_memo(root2))  # 9

Complexity

• Time: O(n) — each node computed once
• Space: O(n) — memo dict + call stack

2. Optimal DFS Returning State Pair

Intuition

Instead of memoizing, we can avoid redundant computation entirely by having the DFS return a pair: (rob, skip) where:

• rob = max money if we rob this node
• skip = max money if we skip this node

The parent can then compute both its own rob/skip values directly from the children’s pairs — no repeated work.

Algorithm

1. Define dfs(node) → (rob, skip) tuple
2. Base case: null node returns (0, 0)
3. For each node:
   • rob = node.val + left_skip + right_skip (rob current → must skip children)
   • skip = max(left_rob, left_skip) + max(right_rob, right_skip) (skip current → take best from each child)
4. Return (rob, skip)
5. Answer is max(dfs(root))

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (rob, skip)

        left_rob, left_skip = dfs(node.left)
        right_rob, right_skip = dfs(node.right)

        # Rob current: must skip both children
        rob_current = node.val + left_skip + right_skip

        # Skip current: take best option from each child independently
        skip_current = max(left_rob, left_skip) + max(right_rob, right_skip)

        return (rob_current, skip_current)

    rob_root, skip_root = dfs(root)
    return max(rob_root, skip_root)

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([3, 2, 3, None, 3, None, 1])
print(rob(root1))  # 7

root2 = build_tree([3, 4, 5, 1, 3, None, 1])
print(rob(root2))  # 9

root3 = build_tree([1])
print(rob(root3))  # 1

# Walk through Example 1 manually:
# Node 1 (leaf, right of 3-right): rob=1, skip=0
# Node 3 (leaf, right of 2): rob=3, skip=0
# Node 3 (root): rob=3+0+0=3, skip=max(3,0)+max(1,0)=3+1=4 → wait
# Actually let's trace Example 1: [3,2,3,null,3,null,1]
#     3
#    / \
#   2   3
#    \   \
#     3   1
# Leaf 3 (under 2): rob=3, skip=0
# Leaf 1 (under 3): rob=1, skip=0
# Node 2: rob=2+0=2, skip=max(3,0)=3
# Node 3 (right): rob=3+0=3, skip=max(1,0)=1
# Root 3: rob=3+skip(2)+skip(3)=3+3+1=7, skip=max(rob2,skip2)+max(rob3,skip3)=max(2,3)+max(3,1)=3+3=6
# Answer: max(7,6) = 7 ✓

Complexity

• Time: O(n) — each node visited exactly once
• Space: O(h) — recursion stack

Common Pitfalls

Confusing “skip child” with “rob grandchild”. When you rob the current node, you must skip the direct children. But you don’t automatically rob the grandchildren — you take the best option from the grandchildren (which is already encoded in left_skip from the children’s DFS return).

Returning a single value from DFS. If DFS only returns the max money, you lose information about whether the current node was robbed or not. The parent needs to know this to decide its own options. Always return both (rob, skip).