Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

• Difficulty: MEDIUM
• Problem: House Robber III
• Topics: Dynamic Programming, Tree, Depth-First Search, Binary Tree

Problem gist

Each node in a binary tree represents a house, and its value is the amount of money in that house. Robbing two houses connected by an edge triggers the alarm, so a robbed node rules out its parent and its immediate children. The goal is to choose a valid set of nodes with the largest possible total value.

A choice near the root affects what is allowed below it, which makes a simple greedy rule unreliable. Taking the largest visible value can block several children whose combined value is better, while skipping a modest value can unlock profitable choices farther down the tree. Trying both choices independently at every node repeats the same subtree work and can take exponential time.

The useful observation is that a parent does not need to know exactly which houses were selected inside a child subtree. It needs only two totals: the best result when that child’s root is robbed, and the best result when it is skipped.

Deriving the optimal solution

For every node, compute a pair of states after its children have been evaluated:

• rob_current: the best total when the current node is robbed.
• skip_current: the best total when the current node is not robbed.

If the current node is robbed, neither child may be robbed. Its first state is therefore:

rob_current = node.val + left.skip_current + right.skip_current

If the current node is skipped, each child is free to use whichever of its two states pays more:

skip_current = max(left.rob_current, left.skip_current) + max(right.rob_current, right.skip_current)

A missing child contributes (0, 0). Once the root’s pair is known, the answer is the larger of its two totals because the root itself is optional.

This is postorder tree dynamic programming: children must be solved before their parent. The recurrence considers both possibilities at every node, but compresses an entire solved subtree into the only two facts its parent can use. That makes the choices complete without recomputing subproblems.

The implementation below performs postorder traversal explicitly instead of recursively. One stack records unfinished tree work, while a second stack holds the completed state pairs. This avoids Python’s recursion-depth limit on a highly skewed tree. Each node and each null child is processed a constant number of times, so the running time is O(n). At most O(h) unfinished work and completed sibling states are retained, where h is the tree height. The worst case is O(n) space for a chain-shaped tree and O(log n) for a balanced tree.

Python solution

from __future__ import annotations

from typing import NamedTuple


# LeetCode provides this class:
# class TreeNode:
#     def __init__(
#         self,
#         value: int = 0,
#         left: TreeNode | None = None,
#         right: TreeNode | None = None,
#     ):
#         self.val = value
#         self.left = left
#         self.right = right


class RobberyState(NamedTuple):
    """Best totals for the two choices at one subtree root."""

    rob_current: int
    skip_current: int


EMPTY_SUBTREE_STATE = RobberyState(rob_current=0, skip_current=0)


class HouseRobberTreePlanner:
    """Compute the maximum safe robbery total for a binary tree."""

    @staticmethod
    def maximum_safe_total(root: TreeNode | None) -> int:
        """Return the best total without selecting adjacent tree nodes."""
        if root is None:
            return 0

        # An unexpanded entry schedules its children. The expanded entry then
        # combines the two child states after both have been evaluated.
        traversal_stack: list[tuple[TreeNode | None, bool]] = [(root, False)]
        evaluated_states: list[RobberyState] = []

        while traversal_stack:
            node, children_evaluated = traversal_stack.pop()

            if node is None:
                evaluated_states.append(EMPTY_SUBTREE_STATE)
                continue

            if not children_evaluated:
                traversal_stack.append((node, True))
                # Push right before left so the left subtree is processed first.
                traversal_stack.append((node.right, False))
                traversal_stack.append((node.left, False))
                continue

            # Postorder traversal leaves the right state above the left state.
            right_state = evaluated_states.pop()
            left_state = evaluated_states.pop()

            rob_current = (
                node.val
                + left_state.skip_current
                + right_state.skip_current
            )
            skip_current = max(left_state) + max(right_state)
            evaluated_states.append(
                RobberyState(
                    rob_current=rob_current,
                    skip_current=skip_current,
                )
            )

        root_state = evaluated_states.pop()
        return max(root_state)


class Solution:
    """LeetCode-compatible entry point."""

    def rob(self, root: TreeNode | None) -> int:
        return HouseRobberTreePlanner.maximum_safe_total(root)

Interview follow-ups

Why are two states per node sufficient?

The only connection between a completed subtree and the rest of the tree is the edge from its root to its parent. From the parent’s perspective, every valid selection inside that subtree falls into one of two categories: the subtree root was robbed, or it was skipped. Choices deeper in the subtree cannot impose any additional restriction on the parent.

Keeping the best total in each category therefore preserves every possibility that an ancestor may need. It also discards irrelevant detail, which is why each node can be combined in constant time. The result is O(n) time instead of the exponential branching produced by reconsidering descendant choices.

How would a recursive solution compare with this iterative one?

A recursive postorder helper can return the same RobberyState pair. It is shorter and naturally mirrors the recurrence, and it uses O(h) call-stack space. On a balanced tree this is only O(log n).

Python’s call stack is the important tradeoff. A valid tree shaped like a long chain can exceed the interpreter’s recursion limit before reaching the leaves. The iterative version retains the same O(n) time and O(h) auxiliary-space bounds while making that depth explicit and safe. In a language with reliable deep recursion or guaranteed shallow inputs, the recursive form may be the simpler production choice.

How can the algorithm return the houses that should be robbed?

Store each node’s two totals in a map during the postorder pass, then reconstruct the selection from the root. If reconstruction enters a node in the robbed state, add that node and force both children into their skipped states. If it enters in the skipped state, choose the larger state independently for each child. A deterministic rule can resolve equal totals if stable output matters.

The total-computation pass remains O(n), and reconstruction visits at most every node once. The tradeoff is O(n) storage for per-node states and decisions instead of the value-only implementation’s O(h) traversal memory. Carrying full node lists inside every dynamic-programming state should be avoided because repeated copying can make the runtime and memory usage quadratic.

What if house values may be negative?

If robbing no house is allowed, the existing recurrence already handles negative values. Missing subtrees contribute zero, and skip_current can propagate the empty selection upward, so the final result never needs to be negative. Robbing a negative-valued node cannot improve the total.

If the rules require at least one house to be robbed, zero can no longer mean both “empty selection” and “valid selection worth zero.” Each state must also record whether it contains a selected node, or use an impossible sentinel for empty choices. That additional validity information preserves O(n) time and O(h) traversal space.

How does the solution generalize to an N-ary tree?

The same two states work because the restriction is still defined by parent-child edges. When the current node is robbed, add skip_current from every child. When it is skipped, add the larger of the two states from every child.

Every edge is examined once, so the runtime remains O(n). The traversal needs O(h) depth-related storage plus space proportional to the widest child list already present in the input. The recurrence changes only from combining two children to iterating over all children.

What if houses within distance two of each other cannot both be robbed?

The parent’s robbed-or-skipped bit is no longer enough because a node must also know whether a robbed ancestor is one or two edges away. One approach is to return a small state table indexed by the distance to the nearest selected ancestor, or equivalently by how many more levels are blocked. Each entry stores the best total under that inherited restriction.

For a fixed distance limit such as two, each node still has only a constant number of states, so the solution remains O(n) time. For a general limit k, the table typically grows to O(k) states per node, producing O(nk) time and O(hk) working space with a depth-first evaluation. The larger state is necessary because more information crosses each parent-child boundary.

Can this dynamic programming solve the same problem on a general graph?

On a tree, removing the parent edge separates the child subtrees, so their best totals can be added independently. A general graph can contain cycles and cross-edges, which means choices in two apparent branches may still conflict. The problem then becomes maximum-weight independent set, which has no known polynomial-time solution for arbitrary graphs unless major complexity assumptions fail.

Special graph families remain tractable. A forest can run the same tree algorithm on every component, while graphs with small treewidth can use dynamic programming over a tree decomposition. The complexity then grows exponentially with the treewidth, illustrating exactly what the original tree structure was buying: a boundary state of only one robbed-or-skipped bit.