337. House Robber III (Medium)

Problem

A thief has found a new place to rob: a neighborhood whose houses are arranged in a binary tree. Each house has some amount of money stashed. The only constraint is that connected houses (a node and its parent) have an automatic alarm that triggers if both are robbed on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without triggering any alarm.

Example

root = [3,2,3,null,3,null,1] → 7 (rob root 3, left-grandchild 3, right-grandchild 1)
root = [3,4,5,1,3,null,1] → 10 (skip root, rob children 4 and 5, plus 5’s child 1)

LeetCode 337 · Link · Medium

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Approach 1: Brute force, top-down recursion with memo

For each node, try both choices: rob it (skip its children, recurse to grandchildren) or skip it (recurse to children). Memoize by node identity.

def rob(root):
    memo = {}                              # L1: O(1) init

    def dfs(node):
        if not node:                       # L2: O(1) base case
            return 0
        if node in memo:                   # L3: O(1) cache hit
            return memo[node]
        # option A: rob this node, must skip children
        rob_this = node.val                # L4: O(1)
        if node.left:
            rob_this += dfs(node.left.left) + dfs(node.left.right)   # L5: grandchildren
        if node.right:
            rob_this += dfs(node.right.left) + dfs(node.right.right) # L6: grandchildren
        # option B: skip this node, children are free
        skip_this = dfs(node.left) + dfs(node.right)                 # L7: O(1) dispatch
        memo[node] = max(rob_this, skip_this)                        # L8: O(1) store
        return memo[node]

    return dfs(root)

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function rob(root: TreeNode | null): number {
    const memo = new Map<TreeNode, number>();  // L1: O(1) init

    function dfs(node: TreeNode | null): number {
        if (!node) return 0;                              // L2: O(1) base case
        if (memo.has(node)) return memo.get(node)!;       // L3: O(1) cache hit
        // option A: rob this node, must skip children
        let robThis = node.val;                           // L4: O(1)
        if (node.left) robThis += dfs(node.left.left) + dfs(node.left.right);   // L5: grandchildren
        if (node.right) robThis += dfs(node.right.left) + dfs(node.right.right);// L6: grandchildren
        // option B: skip this node, children are free
        const skipThis = dfs(node.left) + dfs(node.right);                      // L7: O(1) dispatch
        const best = Math.max(robThis, skipThis);                               // L8: O(1) store
        memo.set(node, best);
        return best;
    }

    return dfs(root);
}

final class Solution { func rob(_ root: TreeNode?) -> Int { var memo: [ObjectIdentifier: Int] = [:]; func solve(_ node: TreeNode?) -> Int { guard let node else { return 0 }; let key = ObjectIdentifier(node); if let cached = memo[key] { return cached }; let take = node.val + solve(node.left?.left) + solve(node.left?.right) + solve(node.right?.left) + solve(node.right?.right); let skip = solve(node.left) + solve(node.right); let best = max(take, skip); memo[key] = best; return best }; return solve(root) } }

Where the time goes, line by line

Variables: n = number of nodes, h = tree height.

Line	Per-call cost	Times executed	Contribution
L2-L3 (base/cache)	$O(1)$	n	$O(n)$
L4 (rob_this init)	$O(1)$	n	$O(n)$
L5/L6 (grandchildren calls)	$O(1)$ dispatch (memoized)	n	$O(n)$
L7 (skip_this calls)	$O(1)$ dispatch	n	$O(n)$
L8 (store memo)	$O(1)$	n	$O(n)$

With memoization every node is computed exactly once. Without it, the same subtrees are recomputed exponentially — grandchildren are reached via two routes (rob parent, or skip parent then rob child).

Complexity

Time: $O(n)$ . Each node computed once via memo.
Space: $O(n)$ for the memo dict, $O(h)$ for the recursion stack.

Approach 2: Post-order DFS returning a pair (optimal)

Instead of memoizing answers per node, return a pair (rob_this, skip_this) from each node. The parent combines them in $O(1)$ with no dict overhead.

def rob(root):
    def dfs(node):
        if not node:                               # L1: O(1) base case
            return (0, 0)                          # L2: (rob, skip) pair
        left = dfs(node.left)                      # L3: O(1) dispatch, returns pair
        right = dfs(node.right)                    # L4: O(1) dispatch, returns pair
        # rob this node: cannot use direct children
        rob_this = node.val + left[1] + right[1]   # L5: O(1), left[1]=skip_left
        # skip this node: children can be robbed or not, take best
        skip_this = max(left) + max(right)         # L6: O(1), best of each child
        return (rob_this, skip_this)               # L7: O(1) return pair

    return max(dfs(root))                          # L8: O(1) take best at root

function rob(root: TreeNode | null): number {
    function dfs(node: TreeNode | null): [number, number] {
        if (!node) return [0, 0];                                    // L1/L2: base case pair
        const [lRob, lSkip] = dfs(node.left);                       // L3: O(1) dispatch
        const [rRob, rSkip] = dfs(node.right);                      // L4: O(1) dispatch
        const robThis = node.val + lSkip + rSkip;                    // L5: O(1)
        const skipThis = Math.max(lRob, lSkip) + Math.max(rRob, rSkip);  // L6: O(1)
        return [robThis, skipThis];                                  // L7: O(1) return pair
    }
    const [robRoot, skipRoot] = dfs(root);
    return Math.max(robRoot, skipRoot);                              // L8: O(1) take best at root
}

final class Solution { func rob(_ root: TreeNode?) -> Int { func solve(_ node: TreeNode?) -> (skip: Int, take: Int) { guard let node else { return (0, 0) }; let left = solve(node.left), right = solve(node.right); return (max(left.skip, left.take) + max(right.skip, right.take), node.val + left.skip + right.skip) }; let result = solve(root); return max(result.skip, result.take) } }

Where the time goes, line by line

Variables: n = number of nodes, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1-L2 (base case)	$O(1)$	h (leaf depth)	$O(h)$
L3/L4 (recurse children)	$O(1)$ dispatch	n	$O(n)$ ← dominates
L5 (rob_this)	$O(1)$	n	$O(n)$
L6 (skip_this)	$O(1)$	n	$O(n)$
L7 (return)	$O(1)$	n	$O(n)$
L8 (final max)	$O(1)$	1	$O(1)$

Each node is visited exactly once in post-order (leaves first, root last). The returned pair encodes both choices so no parent ever needs to revisit a subtree. Eliminates the hash dict entirely.

Complexity

Time: $O(n)$ . Each node visited once, driven by L3/L4.
Space: $O(h)$ for the recursion stack only.

The pair invariant

At every node, dfs(node) returns:

rob_this: best loot if we rob this node (must skip direct children, take best from grandchildren via left[1] and right[1])
skip_this: best loot if we skip this node (each child can be robbed or not independently, hence max(left) and max(right))

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Top-down with memo	$O(n)$	$O(n)$
Post-order pair return	$O(n)$	$O(h)$

The pair-return pattern is canonical for tree DP where each node needs to track multiple states. The same shape solves Binary Tree Cameras (968) and Diameter of Binary Tree (543).

Test cases

Python
TypeScript

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

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

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)
        left = dfs(node.left)
        right = dfs(node.right)
        rob_this = node.val + left[1] + right[1]
        skip_this = max(left) + max(right)
        return (rob_this, skip_this)
    return max(dfs(root))

def _run_tests():
    assert rob(build_tree([3, 2, 3, None, 3, None, 1])) == 7
    assert rob(build_tree([3, 4, 5, 1, 3, None, 1])) == 10
    assert rob(build_tree([5])) == 5
    assert rob(build_tree([1, 2])) == 2
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function rob(root: TreeNode | null): number {
    function dfs(node: TreeNode | null): [number, number] {
        if (!node) return [0, 0];
        const [lRob, lSkip] = dfs(node.left);
        const [rRob, rSkip] = dfs(node.right);
        return [node.val + lSkip + rSkip, Math.max(lRob, lSkip) + Math.max(rRob, rSkip)];
    }
    return Math.max(...dfs(root));
}

console.assert(rob(buildTree([3, 2, 3, null, 3, null, 1])) === 7);
console.assert(rob(buildTree([3, 4, 5, 1, 3, null, 1])) === 10);
console.assert(rob(buildTree([5])) === 5);
console.assert(rob(buildTree([1, 2])) === 2);
console.log("all tests pass");

House Robber, the linear version of this problem
House Robber II, circular array variant
Binary Tree Maximum Path Sum, same post-order pair pattern

Tree Traversal, the recursive or iterative visit pattern for carrying path and subtree state.
Dynamic Programming, the state and transition model for reusing answers to overlapping subproblems.