House Robber III

Medium Trees & BST Postorder + Multiple Return Values Original on LeetCode

House Robber III is a medium trees & bst problem solved with the postorder + multiple return values pattern. The best approach, optimal (postorder with two return values), runs in O(n) time and O(h) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (recursion over grandchildren) up.

Problem

The houses in a neighbourhood are laid out as a binary tree: root is the entrance house, and every house has at most two houses hanging off it. Each node’s value is the cash stored in that house.

A thief may break into any set of houses, but if two houses joined directly by an edge (a parent and its child) are both robbed on the same night, the alarm goes off.

Return the largest amount of cash the thief can collect without setting off the alarm.

Examples

Example 1

Input
root = [5,2,4,null,6,null,3]
Output
14
Why
Take 5, 6 and 3. Node 5 is not directly linked to 6 or 3, so 5 + 6 + 3 = 14.

Example 2

Input
root = [2,9,3,1,1,7]
Output
16
Why
Take 9 and 7: they are cousins, not parent and child, so 9 + 7 = 16.

Example 3

Input
root = [7]
Output
7
Why
A single house: take it.

Constraints

  • The tree has between 1 and 10^4 nodes.
  • 0 <= Node.val <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (recursion over grandchildren)O(φ^h) (exponential)O(h)
Memoized recursionO(n)O(n)
Optimal (postorder with two return values)O(n)O(h)

1Brute force (recursion over grandchildren)

TimeO(φ^h) (exponential)Each subtree is solved again from its parent and its grandparent, so the work grows like Fibonacci numbers along a path.
SpaceO(h)Recursion depth equals the tree height h.

For a node, the best total is the larger of two options: take the node plus the best totals of its four grandchildren, or skip it and add the best totals of its two children. Compute both options with plain recursion.

  1. If the node is null, return 0.
  2. take = node.val + best(left.left) + best(left.right) + best(right.left) + best(right.right) (skip missing children).
  3. skip = best(left) + best(right).
  4. Return max(take, skip).
class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int take = root.val;
        if (root.left != null) take += rob(root.left.left) + rob(root.left.right);
        if (root.right != null) take += rob(root.right.left) + rob(root.right.right);
        int skip = rob(root.left) + rob(root.right);
        return Math.max(take, skip);
    }
}

2Memoized recursion

TimeO(n)Each node's value is computed once; every lookup is O(1) on average.
SpaceO(n)One memo entry per node plus the recursion stack.

The same recursion, but remember the answer for each node in a hash map keyed by the node itself. Every subtree is then solved only once.

  1. If the node is null, return 0. If it is in the memo, return the stored value.
  2. Compute take and skip exactly as in the brute force.
  3. Store max(take, skip) for this node and return it.
class Solution {
    private Map<TreeNode, Integer> memo = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) return 0;
        Integer known = memo.get(root);
        if (known != null) return known;
        int take = root.val;
        if (root.left != null) take += rob(root.left.left) + rob(root.left.right);
        if (root.right != null) take += rob(root.right.left) + rob(root.right.right);
        int skip = rob(root.left) + rob(root.right);
        int best = Math.max(take, skip);
        memo.put(root, best);
        return best;
    }
}

3Optimal (postorder with two return values)

TimeO(n)Each node is visited once and does constant work.
SpaceO(h)No memo table, only the recursion stack of height h.

Let each node return a pair: [best if this node is skipped, best if this node is taken]. If the node is taken, both children must be skipped. If it is skipped, each child is free to be taken or not, so use the larger of its two values. One postorder pass fills every pair.

  1. dfs(null) = [0, 0].
  2. l = dfs(left), r = dfs(right).
  3. taken = node.val + l[0] + r[0].
  4. skipped = max(l[0], l[1]) + max(r[0], r[1]).
  5. Return [skipped, taken]; the answer is the max of the root's pair.
class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) return new int[] { 0, 0 };
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int taken = node.val + l[0] + r[0];
        int skipped = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[] { skipped, taken };
    }
}

Edge cases to test

  • A single node
  • A long chain (every node has one child), which behaves like the line version of the problem
  • A root worth more than all its children together
  • Many zero-valued nodes
  • The best answer skips two levels in a row

Hints

Hint 1

At each node you face one choice: take this node or not. If you take it, its children are off-limits.

Hint 2

A plain recursion that also looks at grandchildren solves it, but it recomputes the same subtrees again and again.

Hint 3

Let every node return two numbers: the best total if it is taken and the best total if it is skipped. A parent can combine those in O(1).

FAQ

What is the best time complexity for House Robber III?

Optimal (postorder with two return values) runs in O(n) time and O(h) extra space. Each node is visited once and does constant work.

Which pattern does House Robber III use?

It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Validate Binary Search Tree, Children Sum in a Binary Tree.

Is there a brute force solution for House Robber III?

Yes. Brute force (recursion over grandchildren) takes O(φ^h) (exponential) time and O(h) space. For a node, the best total is the larger of two options: take the node plus the best totals of its four grandchildren, or skip it and add the best totals of its two children.

Which edge cases should I test for House Robber III?

A single node; A long chain (every node has one child), which behaves like the line version of the problem; A root worth more than all its children together; Many zero-valued nodes; The best answer skips two levels in a row.