Trees crash course ↗ · 176

337. House Robber III

The houses now form a binary tree, and robbing a node forbids robbing its direct children. One post-order DFS returns a pair [robThis, skipThis] per node — the linear rob-vs-skip state machine lifted onto a tree — for a single-pass, linear-time answer.

● MediumTree DPDFSTypeScript

PROBLEM What we're solving

Houses are arranged as a binary tree. The thief can't rob two directly-linked houses (a parent and its child), or the alarm trips. Return the maximum money robbable. For root = [3,2,3,null,3,null,1] the answer is 7 — rob the root 3, plus the two grandchildren 3 and 1 (3 + 3 + 1 = 7); robbing the children 2 and 3 instead would force skipping both the root and grandchildren and yields less.

KEY IDEA Each node returns two answers, not one

Insight →a single number per node can't capture the constraint, because the parent's choice depends on whether the child was robbed. So return a pair: robThis (best for this subtree if we rob this node) and skipThis (best if we leave it). Robbing a node means its children must be skipped, so robThis = val + lSkip + rSkip. Skipping it frees each child to do whatever is best: skipThis = max(lRob, lSkip) + max(rRob, rSkip).

RECURRENCE Post-order: children first, then the pair

0 · Base case. dfs(null) = [0, 0]— an empty subtree loots nothing whether you "rob" it or not.
1 · Recurse (post-order). Get [lRob, lSkip] and [rRob, rSkip] from the children beforescoring this node — you can't decide a node without its subtrees' two answers.
2 · Rob this node. robThis = node.val + lSkip + rSkip. Taking this house forces both children to be left alone, so each contributes its skip value only.
3 · Skip this node. skipThis = max(lRob, lSkip) + max(rRob, rSkip). With this house untouched, each child independently picks its better option.
4 · Answer. Return [robThis, skipThis] upward; at the root the answer is max(robRoot, skipRoot).

Classic confusion → when you skip a node, you do not add lRob + rRob — a skipped node lets each child choose, so you must take max(lRob, lSkip) per child. And when you rob a node you may only add the children's skip values, never max(rob, skip) — otherwise you could illegally rob a parent and its child together.

COST Complexity & alternatives

Naive recursion (rob root, skip root, recompute)

O(2ⁿ)

Grandchildren's subtrees re-solved over and over.

Post-order pair DFS

O(n)

Each node visited once; O(h) recursion stack.

Space note

Returning the [rob, skip] pair fuses the two cases into a single visit, so time is O(n). Extra space is O(h) for the call stack, where h is the tree height — O(log n) balanced, O(n)for a degenerate chain. The naive "rob root vs skip root" recursion (with a separate helper) recomputes grandchildren exponentially; memoizing on the node fixes it, but the pair-return form needs no memo at all.

Pattern transfer → this is the tree analog of the linear House Robber state machine: there, two rolling scalars rob1/rob2track "best ending here vs one back"; here, the two array slots robThis/skipThis ride up the recursion instead of along an array. It's the same "hold both states, combine on the way" idea as Binary Tree Maximum Path Sum(return one value, record another) and any tree-DP where a node's choice constrains its children.

RUN IT Post-order: return [rob, skip] per node

tree (level-order)

step 0 / 11

STARTPost-order DFS. Each node returns a pair [robThis, skipThis]: best loot of its subtree if we rob this node vs if we skip it. Children are solved before their parent.

1class TreeNode {
2  val: number;
3  left: TreeNode | null;
4  right: TreeNode | null;
5  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
6    this.val = val;
7    this.left = left;
8    this.right = right;
9  }
10}
11 
12function rob(root: TreeNode | null): number {
13  // returns [robThis, skipThis]:
14  //   robThis  = best loot of this subtree IF we rob this node
15  //   skipThis = best loot of this subtree IF we leave this node alone
16▶  function dfs(node: TreeNode | null): [number, number] {
17    if (node === null) return [0, 0];          // empty: nothing either way
18 
19    const [lRob, lSkip] = dfs(node.left);      // children first (post-order)
20    const [rRob, rSkip] = dfs(node.right);
21 
22    // rob node => children MUST be skipped
23▶    const robThis = node.val + lSkip + rSkip;
24    // skip node => each child takes its own best (rob or skip)
25▶    const skipThis = Math.max(lRob, lSkip) + Math.max(rRob, rSkip);
26 
27    return [robThis, skipThis];
28  }
29 
30  const [robRoot, skipRoot] = dfs(root);
31▶  return Math.max(robRoot, skipRoot);          // root is free to rob or skip
32}

current nodechild's [rob, skip]robThisskipThisanswer

slowfast

TYPESCRIPT The solution, annotated

houseRobberIII.ts
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 {
  // returns [robThis, skipThis]:
  //   robThis  = best loot of this subtree IF we rob this node
  //   skipThis = best loot of this subtree IF we leave this node alone
  function dfs(node: TreeNode | null): [number, number] {
    if (node === null) return [0, 0];          // empty: nothing either way

    const [lRob, lSkip] = dfs(node.left);      // children first (post-order)
    const [rRob, rSkip] = dfs(node.right);

    // rob node => children MUST be skipped
    const robThis = node.val + lSkip + rSkip;
    // skip node => each child takes its own best (rob or skip)
    const skipThis = Math.max(lRob, lSkip) + Math.max(rRob, rSkip);

    return [robThis, skipThis];
  }

  const [robRoot, skipRoot] = dfs(root);
  return Math.max(robRoot, skipRoot);          // root is free to rob or skip
}

Reading it block by block

The shape of the return. dfs hands back a tuple [robThis, skipThis] for the subtree rooted at node. One number isn't enough: the parent needs to know the best both with and without this node robbed, because its own choice depends on it.

Base case. dfs(null) returns [0, 0] — an empty subtree contributes nothing under either choice, so both slots are zero.

Recurse first (post-order). Pull [lRob, lSkip] and [rRob, rSkip]from the children before combining. You literally cannot fill this node's pair without both children's pairs.

Rob this node. robThis = node.val + lSkip + rSkip. Robbing the parent bans robbing either child, so each child may contribute only its skip value.

Skip this node. skipThis = max(lRob, lSkip) + max(rRob, rSkip). With the parent left alone, each child is unconstrained and picks its own better outcome.

The root answer. After dfs(root), the root may itself be robbed or skipped — return Math.max(robRoot, skipRoot).

Complexity → O(n) time — each node is visited exactly once and does O(1) work — and O(h) recursion-stack space for tree height h(O(log n) balanced, O(n) worst case). No memoization needed: the pair return already encodes both subproblems.

INTERVIEWFollow-ups they'll ask

"Why return a pair instead of one number?"A parent's legal choices depend on whether the child was robbed. A single "best for this subtree" loses that information; the [rob, skip] pair preserves both cases so the parent can combine correctly.
"What does the naive solution look like, and why is it slow?"A helper that tries "rob this node + recurse on grandchildren" vs "skip + recurse on children" recomputes the grandchildren's subtrees repeatedly → O(2ⁿ). Memoizing per node restores O(n); the pair form avoids the memo entirely.
"How does this connect to the array House Robber?"Identical state machine: rob-vs-skip with "rob forbids the neighbor." The array version rolls two scalars left-to-right; the tree version carries the two states up the post-order recursion.
"Reconstruct which houses were robbed?" Record, alongside each pair, whether robThis or skipThis won at each node, then walk down from the root following the winning choice (and forcing children to skip whenever a parent was robbed).

OPTIMAL Tree DP

houseRobberIII.ts
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 {
  // returns [robThis, skipThis]:
  //   robThis  = best loot of this subtree IF we rob this node
  //   skipThis = best loot of this subtree IF we leave this node alone
  function dfs(node: TreeNode | null): [number, number] {
    if (node === null) return [0, 0];          // empty: nothing either way

    const [lRob, lSkip] = dfs(node.left);      // children first (post-order)
    const [rRob, rSkip] = dfs(node.right);

    // rob node => children MUST be skipped
    const robThis = node.val + lSkip + rSkip;
    // skip node => each child takes its own best (rob or skip)
    const skipThis = Math.max(lRob, lSkip) + Math.max(rRob, rSkip);

    return [robThis, skipThis];
  }

  const [robRoot, skipRoot] = dfs(root);
  return Math.max(robRoot, skipRoot);          // root is free to rob or skip
}

ALT 1 Naive recursion + memoization (rob root vs skip root)

O(n) time with memo · O(2ⁿ) without · O(n) space

The direct translation of the choice: either rob this node and recurse on the grandchildren, or skip it and recurse on the children. Without a cache the grandchildren are re-solved exponentially; a per-node memo restores linear time.

approach-2.ts
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>();

  function best(node: TreeNode | null): number {
    if (node === null) return 0;
    const cached = memo.get(node);
    if (cached !== undefined) return cached;

    // Option A: rob node -> skip children, recurse on grandchildren.
    let robIt = node.val;
    if (node.left) robIt += best(node.left.left) + best(node.left.right);
    if (node.right) robIt += best(node.right.left) + best(node.right.right);

    // Option B: skip node -> take the best of each child.
    const skipIt = best(node.left) + best(node.right);

    const ans = Math.max(robIt, skipIt);
    memo.set(node, ans);
    return ans;
  }

  return best(root);
}

Note → Correct and arguably more intuitive, but it reaches two levels down (grandchildren) when robbing, so without the memo the same subtrees are recomputed exponentially. The pair-return DFS encodes both the rob and skip outcomes in a single visit, so it needs no cache and touches each node exactly once.

MNEMONIC The one-liner

"Rob the node ⇒ children skip; skip the node ⇒ children choose. Return the pair."

TRIGGERS When you see _ → reach for _

House Robber but on a tree	post-order DFS returning [rob, skip]
robbing a node bans its children	robThis = val + lSkip + rSkip
node skipped → child free to choose	skipThis = max(lRob,lSkip)+max(rRob,rSkip)
parent choice depends on child choice	carry both states up the recursion

SKELETON The reusable shape

skeleton.ts
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);
    const robThis = node.val + lSkip + rSkip;
    const skipThis = Math.max(lRob, lSkip) + Math.max(rRob, rSkip);
    return [robThis, skipThis];
  }
  return Math.max(...dfs(root));
}

FLASHCARDS Tap to flip

What does dfs(node) return in House Robber III?

A pair [robThis, skipThis]: the best loot of this subtree if we rob this node vs if we skip it.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What does dfs(node) return?

QUESTION 02

How is robThis (the value if this node IS robbed) computed?

QUESTION 03

How is skipThis (the value if this node is NOT robbed) computed?

QUESTION 04

For root = [3,2,3,null,3,null,1], what is the answer?

QUESTION 05

Which traversal order does the algorithm require?

QUESTION 06

Optimal time and space complexity?

QUESTION 07

A common bug computes skipThis as lRob + rRob. Why is that wrong?

QUESTION 08

#337 · House Robber IIIMaximize loot on a binary tree where adjacent (parent–child) houses cannot both be robbed: a post-order DFS returns a [rob, skip] pair per node, the tree analog of the linear House Robber state machine. O(n).Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Each node returns two answers, not one

RECURRENCE Post-order: children first, then the pair

COST Complexity & alternatives

Space note

RUN IT Post-order: return [rob, skip] per node

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Tree DP

ALT 1 Naive recursion + memoization (rob root vs skip root)

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _