House Robber III

Description

A thief is planning to rob houses arranged in the shape of a binary tree. Each node in the tree represents a house, and the value stored in the node is the amount of money in that house.

There is one critical constraint: if the thief robs two directly-linked houses (i.e., a parent and its child), the security system will automatically alert the police.

Given the root of a binary tree where each node contains a non-negative integer representing the money in that house, determine the maximum amount of money the thief can steal without robbing any two adjacent (directly connected) houses.

Examples

Example 1

Input: root = [3, 2, 3, null, 3, null, 1]

Output: 7

Explanation: The tree looks like this:

The thief can rob the root (3), the right grandchild of the left subtree (3), and the right child's right child (1). Total = 3 + 3 + 1 = 7.

The thief cannot rob root (3) AND its children (2, 3) because they are directly linked. Robbing children 2 + 3 + 3 = 8 is also not valid because child 2 and grandchild 3 are directly linked. The optimal choice yields 7.

Example 2

Input: root = [3, 4, 5, 1, 3, null, 1]

Output: 9

Explanation: The tree looks like this:

If the thief robs the root (3) and grandchildren (1 + 3 + 1 = 5), total = 3 + 5 = 8.
But if the thief skips the root and robs children 4 + 5 = 9, that is better.
Total = 9. Note that robbing children 4 and 5 is valid because they are siblings — not parent-child.

Example 3

Input: root = [2]

Output: 2

Explanation: Only one house exists. The thief robs it. Total = 2.

Constraints

1 ≤ number of nodes in the tree ≤ 10^4
0 ≤ Node.val ≤ 10^4

Editorial

Brute Force

Intuition

At every node in the tree, the thief faces a choice: rob this house or skip it.

If the thief robs this house: The thief gains the money at this node but cannot rob either of its direct children. However, the thief can still consider robbing the grandchildren (children of the children). So the total is: node.val + rob(node.left.left) + rob(node.left.right) + rob(node.right.left) + rob(node.right.right).
If the thief skips this house: The thief gains nothing from this node but is free to make the optimal choice at each of its children. So the total is: rob(node.left) + rob(node.right).

The thief picks whichever option yields more money.

Imagine you are picking apples from a family tree of orchards. If you pick apples from a parent orchard, that parent's immediate child orchards are "locked" for the day. But grandchild orchards are fair game. Alternatively, you skip the parent and let the children decide independently. You want the combination that gives you the most apples.

This recursive approach explores every possible combination of rob/skip decisions, resulting in an exponential number of recursive calls because the same subtrees are evaluated many times from different ancestors.

Step-by-Step Explanation

Let's trace through with root = [3, 2, 3, null, 3, null, 1]:

Step 1: At root (value 3), decide: rob or skip?

Step 2: Option A — Rob root (3). Cannot rob children 2 and 3. Must skip to grandchildren.

Left child (2) has no left child → 0. Left child's right child = 3.
Right child (3) has no left child → 0. Right child's right child = 1.
Rob grandchildren: recurse on each grandchild.
rob(grandchild 3) → it's a leaf, rob gives 3. skip gives 0. max = 3.
rob(grandchild 1) → it's a leaf, rob gives 1. skip gives 0. max = 1.
Option A total = 3 + 0 + 3 + 0 + 1 = 7.

Step 3: Option B — Skip root. Free to choose at children.

rob(left child 2): At node 2, rob or skip?
- Rob 2: value 2, grandchildren = none → total = 2.
- Skip 2: rob(right child 3) = 3.
- max(2, 3) = 3.
rob(right child 3): At node 3, rob or skip?
- Rob 3: value 3, grandchildren = none → total = 3.
- Skip 3: rob(right child 1) = 1.
- max(3, 1) = 3.
Option B total = 3 + 3 = 6.

Step 4: Compare Option A (7) vs Option B (6). max = 7.

Result: Maximum robbery = 7.

Brute Force — Exploring All Rob/Skip Decisions — Watch how the recursive brute force explores every possible rob/skip combination at each node, leading to overlapping subproblems and exponential work.

Algorithm

If the node is null, return 0.
Calculate Option A (rob current node):
- Start with node.val
- If left child exists, add rob(left.left) + rob(left.right)
- If right child exists, add rob(right.left) + rob(right.right)
Calculate Option B (skip current node):
- Return rob(left) + rob(right)
Return max(Option A, Option B).

Code

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int rob(TreeNode* root) {
        if (!root) return 0;
        
        // Option A: Rob this node, skip children, recurse on grandchildren
        int robCurrent = root->val;
        if (root->left) {
            robCurrent += rob(root->left->left) + rob(root->left->right);
        }
        if (root->right) {
            robCurrent += rob(root->right->left) + rob(root->right->right);
        }
        
        // Option B: Skip this node, recurse on children
        int skipCurrent = rob(root->left) + rob(root->right);
        
        return max(robCurrent, skipCurrent);
    }
};

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

class Solution:
    def rob(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        # Option A: Rob this node, skip children, recurse on grandchildren
        rob_current = root.val
        if root.left:
            rob_current += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            rob_current += self.rob(root.right.left) + self.rob(root.right.right)
        
        # Option B: Skip this node, recurse on children
        skip_current = self.rob(root.left) + self.rob(root.right)
        
        return max(rob_current, skip_current)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        
        // Option A: Rob this node, skip children, recurse on grandchildren
        int robCurrent = root.val;
        if (root.left != null) {
            robCurrent += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            robCurrent += rob(root.right.left) + rob(root.right.right);
        }
        
        // Option B: Skip this node, recurse on children
        int skipCurrent = rob(root.left) + rob(root.right);
        
        return Math.max(robCurrent, skipCurrent);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each node, we branch into two choices (rob or skip), and the recursive calls overlap — the same subtrees are re-evaluated from different ancestors. The recursion tree grows exponentially. In the worst case, the number of function calls is exponential in the number of nodes.

Space Complexity: O(h)

The recursion stack goes at most h levels deep (the height of the tree). For a skewed tree, h = n, so space is O(n). For a balanced tree, h = log n.

Why This Approach Is Not Efficient

The brute force has exponential time complexity because it recomputes the result for the same nodes repeatedly. For example, when evaluating the root, we call rob(grandchild) directly. But when we later call rob(child), that call internally calls rob(grandchild) again. The same subtree result is computed over and over.

With n up to 10^4 nodes, an O(2^n) approach is completely infeasible — even 2^20 is over a million, and 2^10000 is astronomically large.

The key observation is that the result for any given node depends only on its subtree structure. Once we compute it once, we should store it and reuse it. This is a classic case for memoization — caching results to eliminate redundant work.

Better Approach - DFS with Memoization

Intuition

The brute force recalculates rob(node) many times for the same node. We can fix this by storing the result of each node in a hash map (cache) keyed by the node reference itself.

Before computing rob(node), we first check: "Have I already computed this?" If yes, return the cached answer instantly. If no, compute it using the same rob/skip logic, then store the result before returning.

This is called memoization — the recursive structure stays the same, but we add a lookup table so that each unique subproblem is solved only once.

Think of it like a detective revisiting interview subjects. The first time you interview someone, you write down their statement. If you need to check their story again later, you just look at your notes instead of conducting the entire interview again.

Step-by-Step Explanation

Let's trace through with root = [3, 2, 3, null, 3, null, 1]:

Step 1: Call rob(root=3). Not in cache. Compute both options.

Step 2: Option A (rob root=3): Need grandchildren.

rob(left.left) = rob(null) = 0
rob(left.right) = rob(node 3 leaf). Not in cache. Leaf → max(3, 0) = 3. Cache: {leaf3: 3}
rob(right.left) = rob(null) = 0
rob(right.right) = rob(node 1 leaf). Not in cache. Leaf → max(1, 0) = 1. Cache: {leaf3: 3, leaf1: 1}
Option A = 3 + 0 + 3 + 0 + 1 = 7.

Step 3: Option B (skip root): Need children.

rob(node 2). Not in cache. Compute:
- Rob 2: val 2 + rob(null) + rob(null) = 2 (no left grandchild, no right grandchild from right child)
  - Actually: rob(2.left.left)... but 2 has no left child. rob(2.right) is leaf3, already cached = 3.
  - Wait — rob 2: val 2 + grandchildren. 2 has no left child. 2's right child is leaf3. rob(leaf3.left) = 0, rob(leaf3.right) = 0. So rob option = 2 + 0 + 0 = 2.
- Skip 2: rob(null) + rob(leaf3) = 0 + 3 = 3. (Cache hit on leaf3!)
- max(2, 3) = 3. Cache: {leaf3: 3, leaf1: 1, node2: 3}

Step 4: rob(node 3 right child). Not in cache. Compute:

Rob 3: val 3 + grandchildren. Right child is leaf1. rob(leaf1.left) = 0, rob(leaf1.right) = 0. So rob = 3 + 0 + 0 = 3.
Skip 3: rob(null) + rob(leaf1) = 0 + 1 = 1. (Cache hit on leaf1!)
max(3, 1) = 3. Cache: {leaf3: 3, leaf1: 1, node2: 3, node3r: 3}
Option B = 3 + 3 = 6.

Step 5: max(7, 6) = 7. Cache: {leaf3: 3, leaf1: 1, node2: 3, node3r: 3, root: 7}

Result: 7. Notice cache hits eliminated redundant subtree evaluations.

DFS with Memoization — Cache Eliminates Redundant Work — Watch how the memoization cache prevents recomputing subtree results. Cache hits (shown when a node resolves instantly) are the key speedup over brute force.

Algorithm

Create a hash map cache mapping node references to their computed optimal robbery value. Initialize with null → 0.
Define dfs(node):
- If node is in the cache, return cache[node].
- Calculate Option A (rob current): node.val + grandchildren sums (checking null children).
- Calculate Option B (skip current): dfs(node.left) + dfs(node.right).
- Store cache[node] = max(Option A, Option B) and return it.
Return dfs(root).

Code

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    unordered_map<TreeNode*, int> cache;
    
    int rob(TreeNode* root) {
        if (!root) return 0;
        if (cache.count(root)) return cache[root];
        
        // Option A: Rob this node
        int robCurrent = root->val;
        if (root->left) {
            robCurrent += rob(root->left->left) + rob(root->left->right);
        }
        if (root->right) {
            robCurrent += rob(root->right->left) + rob(root->right->right);
        }
        
        // Option B: Skip this node
        int skipCurrent = rob(root->left) + rob(root->right);
        
        cache[root] = max(robCurrent, skipCurrent);
        return cache[root];
    }
};

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

class Solution:
    def rob(self, root: TreeNode) -> int:
        cache = {None: 0}
        
        def dfs(node):
            if node in cache:
                return cache[node]
            
            # Option A: Rob this node
            rob_current = node.val
            if node.left:
                rob_current += dfs(node.left.left) + dfs(node.left.right)
            if node.right:
                rob_current += dfs(node.right.left) + dfs(node.right.right)
            
            # Option B: Skip this node
            skip_current = dfs(node.left) + dfs(node.right)
            
            cache[node] = max(rob_current, skip_current)
            return cache[node]
        
        return dfs(root)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    private Map<TreeNode, Integer> cache = new HashMap<>();
    
    public int rob(TreeNode root) {
        if (root == null) return 0;
        if (cache.containsKey(root)) return cache.get(root);
        
        // Option A: Rob this node
        int robCurrent = root.val;
        if (root.left != null) {
            robCurrent += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            robCurrent += rob(root.right.left) + rob(root.right.right);
        }
        
        // Option B: Skip this node
        int skipCurrent = rob(root.left) + rob(root.right);
        
        cache.put(root, Math.max(robCurrent, skipCurrent));
        return cache.get(root);
    }
}

Complexity Analysis

Time Complexity: O(n)

Each node is computed at most once and then cached. Every subsequent access to the same node is an O(1) hash map lookup. Since there are n nodes, the total work is O(n).

Space Complexity: O(n)

The cache stores one entry per node, requiring O(n) space. The recursion stack also uses O(h) space where h is the tree height. Total: O(n).

Why This Approach Is Not Efficient

While the memoized approach runs in O(n) time, it uses O(n) extra space for the hash map on top of the O(h) recursion stack. The hash map also has constant-factor overhead from hashing node references.

More fundamentally, the approach still reaches into grandchildren at each node, which complicates the logic. The recursive structure computes rob(node) as a single value — the best you can do for the subtree. But this forces us to look two levels down when deciding to rob the current node.

A cleaner design would have each recursive call return two values: the best result when robbing this node, and the best result when skipping it. This way, each node only communicates with its direct children (not grandchildren), and we eliminate the hash map entirely. The parent can combine the children's two-value results directly.

Optimal Approach - Tree DP with Rob/Skip Pairs

Intuition

Instead of returning a single number from each subtree and needing to peek at grandchildren, we make the recursive function return a pair of values for every node:

withRob: The maximum money if we rob this node.
withoutRob: The maximum money if we skip this node.

How do we compute these?

If we rob this node (withRob): We gain node.val, but we CANNOT rob either child. So from each child, we must use their withoutRob value.
- withRob = node.val + left.withoutRob + right.withoutRob
If we skip this node (withoutRob): We gain nothing from this node, but each child is free to be robbed or skipped — whichever is better.
- withoutRob = max(left.withRob, left.withoutRob) + max(right.withRob, right.withoutRob)

The final answer is max(root.withRob, root.withoutRob).

Think of it like a team decision at each level. Each team member (node) reports two scenarios to their manager: "Here's what I can contribute if I participate, and here's what I can contribute if I sit out." The manager then picks the combination that maximizes the total, respecting the constraint that adjacent participants cannot both be active.

This approach is elegant because:

Each node only talks to its direct children (no grandchild peeking).
No extra hash map is needed — the pair travels up the recursion naturally.
The logic at each node is simple arithmetic on children's pairs.

Binary tree with each node annotated with [withRob, withoutRob] pair values showing bottom-up computation

Step-by-Step Explanation

Let's trace through with root = [3, 2, 3, null, 3, null, 1]:

Step 1: Start DFS at root (3). Recurse into left child (2) first.

Step 2: At node 2, recurse into its left child → null. Return [0, 0].

Step 3: Recurse into node 2's right child (leaf 3).

Leaf 3 has no children. Both children return [0, 0].
withRob = 3 + 0 + 0 = 3.
withoutRob = max(0, 0) + max(0, 0) = 0.
Return [3, 0].

Step 4: Back at node 2. Left child returned [0, 0]. Right child returned [3, 0].

withRob = 2 + left.withoutRob(0) + right.withoutRob(0) = 2.
withoutRob = max(0, 0) + max(3, 0) = 0 + 3 = 3.
Return [2, 3].

Step 5: Back at root (3). Left subtree returned [2, 3]. Now recurse into right child (3).

Step 6: At right child (3), recurse into its left child → null. Return [0, 0].

Step 7: Recurse into right child's right child (leaf 1).

Leaf 1: withRob = 1, withoutRob = 0. Return [1, 0].

Step 8: Back at right child (3). Left child returned [0, 0]. Right child returned [1, 0].

withRob = 3 + 0 + 0 = 3.
withoutRob = max(0, 0) + max(1, 0) = 0 + 1 = 1.
Return [3, 1].

Step 9: Back at root (3). Left returned [2, 3]. Right returned [3, 1].

withRob = 3 + left.withoutRob(3) + right.withoutRob(1) = 3 + 3 + 1 = 7.
withoutRob = max(2, 3) + max(3, 1) = 3 + 3 = 6.
Return [7, 6].

Step 10: Final answer = max(7, 6) = 7.

Tree DP — Computing Rob/Skip Pairs Bottom-Up — Watch how each node computes its [withRob, withoutRob] pair using only its direct children's pairs, then passes the result upward. No hash map, no grandchild peeking.

Algorithm

Define a helper dfs(node) that returns a pair [withRob, withoutRob].
Base case: if node is null, return [0, 0].
Recursively get leftPair = dfs(node.left) and rightPair = dfs(node.right).
Compute:
- withRob = node.val + leftPair[1] + rightPair[1] (rob this, children must be skipped)
- withoutRob = max(leftPair[0], leftPair[1]) + max(rightPair[0], rightPair[1]) (skip this, children free to choose)
Return [withRob, withoutRob].
The answer is max(dfs(root)).

Code

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int rob(TreeNode* root) {
        auto result = dfs(root);
        return max(result.first, result.second);
    }
    
    // Returns {withRob, withoutRob}
    pair<int, int> dfs(TreeNode* node) {
        if (!node) return {0, 0};
        
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        
        int withRob = node->val + left.second + right.second;
        int withoutRob = max(left.first, left.second)
                       + max(right.first, right.second);
        
        return {withRob, withoutRob};
    }
};

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

class Solution:
    def rob(self, root: TreeNode) -> int:
        def dfs(node):
            if not node:
                return [0, 0]
            
            left_pair = dfs(node.left)
            right_pair = dfs(node.right)
            
            with_rob = node.val + left_pair[1] + right_pair[1]
            without_rob = max(left_pair) + max(right_pair)
            
            return [with_rob, without_rob]
        
        return max(dfs(root))

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public int rob(TreeNode root) {
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }
    
    // Returns [withRob, withoutRob]
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        
        int withRob = node.val + left[1] + right[1];
        int withoutRob = Math.max(left[0], left[1])
                       + Math.max(right[0], right[1]);
        
        return new int[]{withRob, withoutRob};
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each node exactly once. At each node, we perform a constant amount of work: two additions and two max operations. Total: O(n).

Space Complexity: O(h)

The only space used is the recursion call stack, which goes as deep as the tree's height h. In the worst case (skewed tree), h = n → O(n). For a balanced tree, h = log n → O(log n).

Compared to the memoized approach, we eliminated the O(n) hash map entirely. The pair values are returned on the stack and never stored globally. This gives the same O(n) time with strictly less space overhead — just the recursion stack.

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

House Robber III

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - DFS with Memoization

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Tree DP with Rob/Skip Pairs

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis