House Robber III

Pair-returning DFS (rob vs skip)

House Robber on a tree. Return (rob_this, skip_this) pair from each subtree.

Published Apr 17, 2026

Problem

Houses are arranged as a binary tree. Two directly connected houses (parent ↔ child) cannot both be robbed on the same night. Return the maximum money you can rob.

Input

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

Output

Explanation

Rob root (3) + two grandchildren (3 + 1) = 7.

Input

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

Output

Explanation

Skip root; rob both children (4 + 5) = 9.

Input

root = [1]

Output

Intuition

This is #198 House Robber on a tree. Each node has the same two choices — rob or skip — but "adjacent" now means "parent or child" instead of "next index." The recurrence carries over cleanly:

rob(node) = node.val + skip(left) + skip(right)
skip(node) = max(rob, skip)(left) + max(rob, skip)(right)

The naive memoization uses a HashMap<(NodeRef, bool), i32> keyed on (node, parent-robbed). That's O(n) states and O(n) time — fine, but the hash overhead is annoying.

There's a cleaner form: each DFS call returns a pair (rob_this, skip_this). The parent combines children's pairs in constant work:

rob_parent = parent.val + left.skip + right.skip
skip_parent = max(left.rob, left.skip) + max(right.rob, right.skip)

Final answer: max(rob_root, skip_root). No memoization needed — the recursion visits each node exactly once, and the pair return threads both states through the tree in a single post-order pass.

Approach

Memoized (node, parent-robbed)

TimeO(n)

SpaceO(n)

Explicit memoization. Two entries per node (one for each parent-robbed state). Works; allocates a hashmap.

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;

impl Solution {
    pub fn rob(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn go(
            node: &Option<Rc<RefCell<TreeNode>>>,
            parent_robbed: bool,
            memo: &mut HashMap<(*const TreeNode, bool), i32>,
        ) -> i32 {
            let Some(n) = node else { return 0 };
            let key = (n.as_ptr() as *const TreeNode, parent_robbed);
            if let Some(&v) = memo.get(&key) {
                return v;
            }
            let n_ref = n.borrow();
            let skip = go(&n_ref.left, false, memo) + go(&n_ref.right, false, memo);
            let v = if parent_robbed {
                skip
            } else {
                let rob_here = n_ref.val + go(&n_ref.left, true, memo) + go(&n_ref.right, true, memo);
                rob_here.max(skip)
            };
            memo.insert(key, v);
            v
        }
        let mut memo = HashMap::new();
        go(&root, false, &mut memo)
    }
}

Rust · runnable

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

function rob(root: TreeNode | null): number {
  const memo = new Map<TreeNode, { robbed: number; notRobbed: number }>();
  const go = (node: TreeNode | null, parentRobbed: boolean): number => {
    if (!node) return 0;
    const cached = memo.get(node);
    if (cached) return parentRobbed ? cached.robbed : cached.notRobbed;
    const skip = go(node.left, false) + go(node.right, false);
    const robHere = node.val + go(node.left, true) + go(node.right, true);
    const result = { robbed: skip, notRobbed: Math.max(robHere, skip) };
    memo.set(node, result);
    return parentRobbed ? result.robbed : result.notRobbed;
  };
  return go(root, false);
}

TypeScript · runnable

Pair-Returning DFS

TimeO(n)

SpaceO(h)

Recommended

The clean form: every DFS call returns (rob, skip) for the current subtree's root. The caller just combines two children's pairs using the recurrence above. No hashmap, no auxiliary table — constant work per node.

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn rob(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn go(node: &Option<Rc<RefCell<TreeNode>>>) -> (i32, i32) {
            let Some(n) = node else { return (0, 0) };
            let n = n.borrow();
            let (l_rob, l_skip) = go(&n.left);
            let (r_rob, r_skip) = go(&n.right);
            let rob_here = n.val + l_skip + r_skip;
            let skip_here = l_rob.max(l_skip) + r_rob.max(r_skip);
            (rob_here, skip_here)
        }
        let (r, s) = go(&root);
        r.max(s)
    }
}

Rust · runnable

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

TypeScript · runnable

Trace

Post-order pair walk on [3, 2, 3, null, 3, null, 1]:

node	left pair	right pair	(rob, skip)
3 (leaf)	(0, 0)	(0, 0)	(3, 0)
2	(0, 0)	(3, 0)	(2, 3)
1 (leaf)	(0, 0)	(0, 0)	(1, 0)
3 (mid-right)	(0, 0)	(1, 0)	(3, 1)
3 (root)	(2, 3)	(3, 1)	(3+3+1, max(2,3)+max(3,1)) = (7, 6)

Return max(7, 6) = 7. ✓

Edge cases

Empty tree — return 0. The base case (0, 0) handles this.
Single node — return node.val. No children, so (val, 0); max picks val.
Skew tree — the algorithm is indifferent to shape. O(h) space matches the recursion depth; worst case O(n) for a linked-list-like tree.
Negative values — not in LC's constraints, but the algorithm still computes the right answer (skip can beat rob when val is negative).

ℹ️

Note

Tree DP with pair returns generalizes beyond "rob or skip." Many tree problems have a similar shape: each node reports a small fixed number of states to its parent, and the parent combines them locally. #124 Max Path Sum returns "best path through this subtree, rooted or not"; #968 Binary Tree Cameras returns three states (covered, camera, needs-cover). Identifying the minimal state each subtree needs to report is the core tree-DP skill.

Takeaway

House Robber III teaches a move you'll reuse constantly: instead of recursing twice per state, recurse once and return a tuple. This pattern — carry the multi-state answer up the tree in one pass — applies to any problem where a node's contribution depends on a finite number of ways it can "behave."

The same reframe works on linear DP. Many 1D problems can be rewritten to carry (best_with_last_taken, best_without_last_taken) forward through the loop. That's exactly what #198's (prev1, prev2) pair is, unrolled. Tree DP makes the structural parallel visible.