House Robber III: Tree DP

You know how to rob a row of houses and a circular street. Now the houses are arranged in a binary tree, with alarms linking every parent to its children. Rob any set of nodes you like, but never two nodes that share a direct edge.

This is LeetCode 337: House Robber III. If you have not worked through House Robber or House Robber II, start there. The core constraint is the same: no two directly connected houses can both be robbed. What changes is the shape of the data structure.

Why this problem matters

Tree DP is one of the most common interview archetypes, and House Robber III is its clearest introduction. The insight that each node can return a pair of values, one for each local choice, is the foundation of dozens of harder tree problems.

Once you see how to carry two states up the tree, you will recognize the same pattern in Binary Tree Maximum Path Sum, diameter calculations, and tree coloring problems. The post-order traversal structure, process children first then combine at the parent, is a template you will reuse constantly.

Thinking it through

At every node you face the same two options: rob it or skip it.

If you rob a node, you cannot rob either of its children. But you can rob its grandchildren. So the money from robbing a node is its own value plus the best you can get from each subtree when those children are skipped.

If you skip a node, its children are unconstrained. Each child can be robbed or skipped, whichever gives more money. So the money from skipping a node is the best outcome for the left subtree plus the best outcome for the right subtree.

The problem is that the best outcome for a child depends on a choice you have not made yet when you visit that child. This is why the trick is to return both outcomes from every node. You delay the final decision until the parent has everything it needs.

The post-order pair DP

Every recursive call returns a pair (rob_this, skip_this):

• rob_this: maximum money when you rob this node
• skip_this: maximum money when you skip this node

At a null node both values are 0. That is the base case.

For any real node, once you have the pairs from both children:

rob_this = node.val + left_skip + right_skip
skip_this = max(left_rob, left_skip) + max(right_rob, right_skip)

When you rob this node you add its value plus the skip values from both children (because robbing this node forces both children to be skipped). When you skip this node, each child is free to be robbed or skipped, so you take the max of each child's pair and add them.

The final answer at the root is max(rob_root, skip_root).

Clean Python solution

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)
        left_rob, left_skip = dfs(node.left)
        right_rob, right_skip = dfs(node.right)
        rob_this = node.val + left_skip + right_skip
        skip_this = max(left_rob, left_skip) + max(right_rob, right_skip)
        return (rob_this, skip_this)
    rob_root, skip_root = dfs(root)
    return max(rob_root, skip_root)

The DFS visits every node exactly once in post-order: left subtree, right subtree, then current node. Each call does O(1) work. The whole tree is processed bottom-up, so by the time you compute the root's pair, every subtree answer is already baked in.

Step-by-step walkthrough

The diagram below traces the DP pairs for the tree [3,2,3,null,3,null,1]. Each node card shows the (rob, skip) pair once it has been computed. The active node at each step is highlighted in blue.

Working through the example by hand:

• The two leaf grandchildren return (3, 0) and (1, 0).
• Node 2 (value=2, one child with pair (3, 0)): rob = 2 + 0 = 2, skip = max(3,0) = 3. Returns (2, 3).
• Node 3 right child (value=3, one child with pair (1, 0)): rob = 3 + 0 = 3, skip = max(1,0) = 1. Returns (3, 1).
• Root (value=3, left=(2,3), right=(3,1)): rob = 3 + 3 + 1 = 7, skip = max(2,3) + max(3,1) = 3 + 3 = 6. Returns (7, 6).
• Answer: max(7, 6) = 7.

Complexity analysis

Every node is visited once, so time is O(n) where n is the number of nodes. The space is the call stack depth, which equals the height h of the tree. For a balanced tree h = O(log n). For a completely skewed tree h = O(n) in the worst case.

There is no extra data structure: the two values per node are returned through the call stack itself, not stored in a hash map or array.

Building blocks

This solution combines two fundamental techniques:

Post-order traversal: you process both children before doing anything at the current node. The post-order guarantee means that when you compute a node's pair, the children's pairs are already ready.

DP on trees: instead of a 1D or 2D DP table, your state lives at each node. Each node's state is a small tuple that captures all the locally relevant choices. Choices from lower nodes propagate up without needing to store them globally.

Together these form the template for tree DP: recurse to leaves, return a meaningful state, combine children's states at the parent, propagate up.

Edge cases to watch for

• Single node: the tree has only a root. dfs returns (root.val, 0). The answer is root.val. Works correctly.
• All left-skewed tree (a linked list leaning left): every node has only a left child. The tree height is n, so the call stack goes n levels deep. The algorithm is still correct; just be aware of the O(n) space usage.
• All nodes have the same value: say every node holds 5. The algorithm handles this correctly because it evaluates both choices at every node. The optimal selection is still determined by the tree structure, not the values.
• Root with null children: the root is a leaf. Same as the single-node case.

From understanding to recall

You now have the core insight: return a pair from every node, compute both choices at each level, and let the parent merge them. But coding this cleanly under time pressure is a separate skill.

The gap between reading a solution and writing it from scratch is real. With spaced repetition, you revisit the pair-return pattern at increasing intervals, reproduce the dfs function without hints each time, and after a few sessions it becomes automatic. You stop asking yourself "wait, do I add rob or skip from the children?" because your hands already know.

The failure mode for most candidates is conflating rob and skip: they add left_rob when they should add left_skip, or they forget to take the max at the skip case. Drilling the formula until it is reflexive eliminates that error.

Related posts

• House Robber - The linear version: same no-adjacent constraint on an array
• House Robber II - The circular version: linear DP applied twice
• Binary Tree Maximum Path Sum - Another post-order tree DP where each node returns a meaningful value to its parent