{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

House Robber III – Solution & Complexity

Interview solutions
/
House Robber III

Solution Walkthrough

  1. Step 1: Understand the constraint on the tree

    • Robbing a house forbids robbing its parent and its direct children.
    • At every node you face a binary choice: rob this node (and skip its children) or skip it (and freely choose within each child).
    • This is the linear House Robber idea lifted onto a tree.

  2. Step 2: Start from the naive recursion

    • If you rob the current node, add its value plus the best of each grandchild subtree.
    • If you skip it, add the best of each child subtree.
    • Take the larger of the two. This is correct but recomputes grandchildren over and over.
    def rob(root: TreeNode) -> int:
    if root is None:
        return 0

    rob_this = root.val
    if root.left is not None:
        rob_this += rob(root.left.left) + rob(root.left.right)
    if root.right is not None:
        rob_this += rob(root.right.left) + rob(root.right.right)

    skip_this = rob(root.left) + rob(root.right)
    return max(rob_this, skip_this)

  3. Step 3: Return two values per node

    • Have each DFS call return a pair: the best loot if this node is robbed and the best if it is not.
    • robbed = node.val + skip(left) + skip(right) (children must be skipped).
    • notRobbed = max(child options) summed over both children.

  4. Step 4: Optimal single postorder pass

    • Combine both children's pairs in O(1) at each node, with no recomputation.
    • The answer is the better of the two options at the root.
    def rob(root: TreeNode) -> int:
    def dfs(node: TreeNode | None) -> tuple[int, int]:
        if node is None:
            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))

  5. Step 5: Dry run

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

    node(rob, skip)
    leaf 3 (under left 2)(3, 0)
    left child 2(2, 3)
    leaf 1 (under right 3)(1, 0)
    right child 3(3, 1)
    root 3(3 + 3 + 1, max(2,3)+max(3,1)) = (7, 6)

    The answer is max(7, 6) = 7.

  6. Step 6: Common mistakes and follow-ups

    • Only tracking a single number per node, which forces expensive grandchild recomputation.
    • When robbing a node, adding the child's robbed value instead of its skipped value.
    • Forgetting that an empty tree returns 0.
    • Follow-up: how would you also return which houses were robbed?

  7. Step 7: Edge cases to test mentally

    • An empty tree yields 0; a single node yields its own value.
    • A straight chain alternates robbed/skipped levels.
    • Sometimes robbing every leaf beats robbing the root plus grandchildren, so always compare both options at the root.

  8. Step 8: Final full solution and complexity

    A single postorder DFS returns each node's (robbed, skipped) best totals and combines children in O(1). Time is O(n) and stack space is O(h) for tree height h.

    def rob(root: TreeNode) -> int:
    def dfs(node: TreeNode | None) -> tuple[int, int]:
        if node is None:
            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))

FAQ

See also

Practice House Robber III online (run code in the browser)Binary Tree Maximum Path Sum solution (hard)Balanced Binary Tree solution (easy)Binary Tree Inorder Traversal solution (easy)Binary Tree Postorder Traversal solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?