House Robber III (LeetCode 337)
The houses in a neighbourhood are joined like a binary tree. The only way in is the house at root, and every other house is reached from exactly one house above it, its parent. A node's value is the money inside that house.
A burglar may break into any set of houses on one night, with one rule: if two houses joined by an edge (a parent and its child) are both broken into, the alarm goes off. Return the most money the burglar can take without ever breaking into both ends of an edge.
Worked Examples
root = [3,2,3,null,3,null,1]7root = [3,4,5,1,3,null,1]9⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[1, 104].0 <= Node.val <= 104
Core Insight
One number per subtree hides whether the child was robbed, so each subtree returns two: the best total with its root robbed and with it skipped. A robbed parent adds its children's skipped totals, a skipped parent adds each child's better total, and the root takes the better of its own two.
Real-World Scenario & Production Applications
Picking people from an org chart so that nobody is picked together with their direct manager, while maximizing a total score, is the same problem: textbooks call it planning a company party. Any hierarchy with a parent-child exclusion rule, such as not scheduling a service and the one it directly depends on in the same maintenance window, has this shape.
Step-by-Step Execution Trace Table
Example 1, root = [3,2,3,null,3,null,1], in postorder (each row is one dfs(node) returning):
| Step | node | left (rob, skip) | right (rob, skip) | rob_this = node.val + left_skip + right_skip | skip_this = max(left) + max(right) | Returns |
|---|---|---|---|---|---|---|
| 1 | 3, the right child of 2 | (0, 0) | (0, 0) | 3 + 0 + 0 = 3 | 0 + 0 = 0 | (3, 0) |
| 2 | 2 | (0, 0) | (3, 0) | 2 + 0 + 0 = 2 | 0 + 3 = 3 | (2, 3) |
| 3 | 1, the right child of the right 3 | (0, 0) | (0, 0) | 1 + 0 + 0 = 1 | 0 + 0 = 0 | (1, 0) |
| 4 | 3, the right child of the root | (0, 0) | (1, 0) | 3 + 0 + 0 = 3 | 0 + 1 = 1 | (3, 1) |
| 5 | 3, the root | (2, 3) | (3, 1) | 3 + 3 + 1 = 7 | 3 + 3 = 6 | (7, 6) |
| End | max(7, 6) = 7 |
At step 2, taking the right child's best, max(3, 0) = 3, in rob_this would give 2 + 0 + 3 = 5: house 2 robbed together with the 3 below it. Carried up, that mistake makes the root report 12.
root = [3,2,3,null,3,null,1]7Example 1, root = [3,2,3,null,3,null,1], in postorder (each row is one dfs(node) returning):
| Step | node | left (rob, skip) | right (rob, skip) | rob_this = node.val + left_skip + right_skip | skip_this = max(left) + max(right) | Returns |
|---|---|---|---|---|---|---|
| 1 | 3, the right child of 2 | (0, 0) | (0, 0) | 3 + 0 + 0 = 3 | 0 + 0 = 0 | (3, 0) |
| 2 | 2 | (0, 0) | (3, 0) | 2 + 0 + 0 = 2 | 0 + 3 = 3 | (2, 3) |
| 3 | 1, the right child of the right 3 | (0, 0) | (0, 0) | 1 + 0 + 0 = 1 | 0 + 0 = 0 | (1, 0) |
| 4 | 3, the right child of the root | (0, 0) | (1, 0) | 3 + 0 + 0 = 3 | 0 + 1 = 1 | (3, 1) |
| 5 | 3, the root | (2, 3) | (3, 1) | 3 + 3 + 1 = 7 | 3 + 3 = 6 | (7, 6) |
| End | max(7, 6) = 7 |
At step 2, taking the right child's best, max(3, 0) = 3, in rob_this would give 2 + 0 + 3 = 5: house 2 robbed together with the 3 below it. Carried up, that mistake makes the root report 12.
| 1 | One number per subtree can't tell the parent whether the child was robbed, so `dfs(node)` returns two: `(rob_this, skip_this)`, the best total in `node`'s subtree when `node` is robbed and when it is skipped. |
| 2 | The parent applies the rule: a robbed node needs both children skipped, a skipped node lets each child take its better state. Answer with `max(dfs(root))`, since the root may be either. |
| 3 | The shape: `if not node: return (0, 0)`; `left_rob, left_skip = dfs(node.left)`; `right_rob, right_skip = dfs(node.right)`; build `rob_this` and `skip_this`; `return (rob_this, skip_this)`. |
| 4 | The trap: `rob_this = node.val + left_skip + right_skip`, never `node.val + max(left_rob, left_skip) + ...`: on `[3,2,3,null,3,null,1]` taking the child's max returns 12 instead of 7. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Bottom-Up DFS lets every subtree hand its parent one finished number. House Robber III breaks that: the best total for a subtree depends on whether its root is robbed, and the parent needs to know which, because a robbed parent can't sit on top of a robbed child. So each subtree hands up one best total per state of its root: (rob_this, skip_this). The parent picks from those states under the rule, and nothing below the children is ever looked at again. That is Tree State DP: the House Robber recurrence of Linear DP, moved onto a tree.
🏢 The Analogy: Two Numbers From Every Team
A company picks staff for a weekend shift, and no one may work it together with their direct manager. Each team lead sends up two numbers: the best total the team can give if the lead works, and if the lead stays home. The lead's own manager never asks for names. If she works, she adds each team's stays-home number; if she stays home, she adds each team's larger number. One number per team would not be enough: she couldn't tell whether it already counts the lead she may not work with.
🔑 Why It Works
Each pair is final when it is returned: rob_this and skip_this both respect the rule everywhere below node. The rule only links a node to its children, so the parent enforces it with the children's states alone. The trap sits on the rob_this line: a child's better state, max(left_rob, left_skip), may be the one where the child is robbed, so a robbed node adds left_skip, never the child's max.
Adding
max(left_rob, left_skip)torob_thisAdding
left_rob + right_robtoskip_thisReturning
dfs(root)[0]instead ofmax(dfs(root))Recursing into grandchildren instead of returning both states
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Binary tree" plus a rule between directly linked nodes ("both ends of an edge") plus "the most money": every node is a yes/no choice, and which choices are allowed depends on the children's choices. That is the signal for Tree State DP: each node returns one best total per state it can be in.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
A robbed node needs both children skipped: rob_this = node.val + left_skip + right_skip. A skipped node lets each child take its better state: skip_this = max(left_rob, left_skip) + max(right_rob, right_skip). The answer is max(dfs(root)).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
rob_thisaddsleft_skip + right_skip, never a child's better state.Call
dfsonce per child and unpack the pair (left_rob, left_skip = dfs(node.left)). Readingdfs(node.left)[1]forrob_thisand callingdfs(node.left)again forskip_thissolves every subtree twice per level: on a chain of 20 houses that is over 4 million calls instead of 41.If you memoize the grandchildren version instead, key the memo by the node itself, never by
node.val: different houses can hold the same amount, and a value key hands one house's answer to another.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Tree State DP. The rule links each house to its parent, so one number per subtree isn't enough: the parent needs to know whether its child was robbed. So my DFS returns two numbers for every node: the best total in its subtree if the node is robbed, and if it is skipped. I compute them in postorder. If I rob the node, both children must be skipped, so rob_this is node.val plus the two children's skip values. If I skip it, each child is free, so skip_this adds the larger of each child's two values. The answer is the larger of the root's two. The trap is robbing a node on top of a child's best total: that best may already rob the child, which breaks the rule. Each node is solved once, so it's
O(N)time and O(H) recursion stack.
Complexity & Mathematical Proof
O(N)
Look at the code: dfs is called once for every node and once for every empty child slot, and a tree with N nodes has N + 1 empty slots, so there are 2N + 1 calls. Each call does O(1) work: two tuple unpacks, one sum for rob_this, and two max calls and one sum for skip_this. No subtree is solved twice, because each call hands both of its states up and the parent reuses them instead of calling dfs on a grandchild. Total: O(N).
O(H) recursion stack
The recursion goes down one level per call, so the call stack holds at most H + 1 frames, where H is the height of the tree: about log N when it is balanced, and N on a chain. Each frame keeps four integers. The answer is one integer.
Derivation Progression
N + (N + 1) = 2N + 1
dfs runs once per node and once per empty child slot, where if not node: return (0, 0) answers at once.
O(1)
Unpack left_rob, left_skip and right_rob, right_skip, add up rob_this, take two max values for skip_this, return the pair.
each subtree solved once
The parent reuses the pair its child returned; it never calls dfs on a grandchild, which is what makes the brute force exponential.
O(N)
2N + 1 calls, O(1) each, then one max at the root.
Variable Definitions
Number of nodes (houses) in the tree
Height of the tree: about log N when balanced, up to N on a chain
Memory Architecture & Bounds
O(H): one frame per level of the current root-to-node path
O(1): each frame keeps four integers, no extra structure
O(1): one integer
Boundary Best / Worst Cases
time and an stack on a balanced tree
time; the stack depth is the tree height
time and an stack on a chain
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "binary tree", "both ends of an edge", "the most money". A yes/no choice at every node plus a rule between a parent and its child: Tree State DP, where each node returns one best total per state it can be in.
nodes and values up to , so any total stays below . Trying every set of houses is ; recursing on grandchildren without saving results is exponential in the height; returning both states is time and an recursion stack.
A chain of houses is calls deep, past the default recursion limit of many runtimes (CPython's is 1000): raise the limit or run the same postorder with an explicit stack. Memoizing rob(node) in a hash map keyed by node also reaches , but pays for an extra map of entries; returning the pair needs no map at all.
House Robber III (LeetCode 337)
The houses in a neighbourhood are joined like a binary tree. The only way in is the house at root, and every other house is reached from exactly one house above it, its parent. A node's value is the money inside that house.
A burglar may break into any set of houses on one night, with one rule: if two houses joined by an edge (a parent and its child) are both broken into, the alarm goes off. Return the most money the burglar can take without ever breaking into both ends of an edge.
Worked Examples
root = [3,2,3,null,3,null,1]7root = [3,4,5,1,3,null,1]9⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[1, 104].0 <= Node.val <= 104
Core Insight
One number per subtree hides whether the child was robbed, so each subtree returns two: the best total with its root robbed and with it skipped. A robbed parent adds its children's skipped totals, a skipped parent adds each child's better total, and the root takes the better of its own two.
Real-World Scenario & Production Applications
Picking people from an org chart so that nobody is picked together with their direct manager, while maximizing a total score, is the same problem: textbooks call it planning a company party. Any hierarchy with a parent-child exclusion rule, such as not scheduling a service and the one it directly depends on in the same maintenance window, has this shape.
Step-by-Step Execution Trace Table
Example 1, root = [3,2,3,null,3,null,1], in postorder (each row is one dfs(node) returning):
| Step | node | left (rob, skip) | right (rob, skip) | rob_this = node.val + left_skip + right_skip | skip_this = max(left) + max(right) | Returns |
|---|---|---|---|---|---|---|
| 1 | 3, the right child of 2 | (0, 0) | (0, 0) | 3 + 0 + 0 = 3 | 0 + 0 = 0 | (3, 0) |
| 2 | 2 | (0, 0) | (3, 0) | 2 + 0 + 0 = 2 | 0 + 3 = 3 | (2, 3) |
| 3 | 1, the right child of the right 3 | (0, 0) | (0, 0) | 1 + 0 + 0 = 1 | 0 + 0 = 0 | (1, 0) |
| 4 | 3, the right child of the root | (0, 0) | (1, 0) | 3 + 0 + 0 = 3 | 0 + 1 = 1 | (3, 1) |
| 5 | 3, the root | (2, 3) | (3, 1) | 3 + 3 + 1 = 7 | 3 + 3 = 6 | (7, 6) |
| End | max(7, 6) = 7 |
At step 2, taking the right child's best, max(3, 0) = 3, in rob_this would give 2 + 0 + 3 = 5: house 2 robbed together with the 3 below it. Carried up, that mistake makes the root report 12.
root = [3,2,3,null,3,null,1]7Example 1, root = [3,2,3,null,3,null,1], in postorder (each row is one dfs(node) returning):
| Step | node | left (rob, skip) | right (rob, skip) | rob_this = node.val + left_skip + right_skip | skip_this = max(left) + max(right) | Returns |
|---|---|---|---|---|---|---|
| 1 | 3, the right child of 2 | (0, 0) | (0, 0) | 3 + 0 + 0 = 3 | 0 + 0 = 0 | (3, 0) |
| 2 | 2 | (0, 0) | (3, 0) | 2 + 0 + 0 = 2 | 0 + 3 = 3 | (2, 3) |
| 3 | 1, the right child of the right 3 | (0, 0) | (0, 0) | 1 + 0 + 0 = 1 | 0 + 0 = 0 | (1, 0) |
| 4 | 3, the right child of the root | (0, 0) | (1, 0) | 3 + 0 + 0 = 3 | 0 + 1 = 1 | (3, 1) |
| 5 | 3, the root | (2, 3) | (3, 1) | 3 + 3 + 1 = 7 | 3 + 3 = 6 | (7, 6) |
| End | max(7, 6) = 7 |
At step 2, taking the right child's best, max(3, 0) = 3, in rob_this would give 2 + 0 + 3 = 5: house 2 robbed together with the 3 below it. Carried up, that mistake makes the root report 12.
| 1 | One number per subtree can't tell the parent whether the child was robbed, so `dfs(node)` returns two: `(rob_this, skip_this)`, the best total in `node`'s subtree when `node` is robbed and when it is skipped. |
| 2 | The parent applies the rule: a robbed node needs both children skipped, a skipped node lets each child take its better state. Answer with `max(dfs(root))`, since the root may be either. |
| 3 | The shape: `if not node: return (0, 0)`; `left_rob, left_skip = dfs(node.left)`; `right_rob, right_skip = dfs(node.right)`; build `rob_this` and `skip_this`; `return (rob_this, skip_this)`. |
| 4 | The trap: `rob_this = node.val + left_skip + right_skip`, never `node.val + max(left_rob, left_skip) + ...`: on `[3,2,3,null,3,null,1]` taking the child's max returns 12 instead of 7. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Bottom-Up DFS lets every subtree hand its parent one finished number. House Robber III breaks that: the best total for a subtree depends on whether its root is robbed, and the parent needs to know which, because a robbed parent can't sit on top of a robbed child. So each subtree hands up one best total per state of its root: (rob_this, skip_this). The parent picks from those states under the rule, and nothing below the children is ever looked at again. That is Tree State DP: the House Robber recurrence of Linear DP, moved onto a tree.
🏢 The Analogy: Two Numbers From Every Team
A company picks staff for a weekend shift, and no one may work it together with their direct manager. Each team lead sends up two numbers: the best total the team can give if the lead works, and if the lead stays home. The lead's own manager never asks for names. If she works, she adds each team's stays-home number; if she stays home, she adds each team's larger number. One number per team would not be enough: she couldn't tell whether it already counts the lead she may not work with.
🔑 Why It Works
Each pair is final when it is returned: rob_this and skip_this both respect the rule everywhere below node. The rule only links a node to its children, so the parent enforces it with the children's states alone. The trap sits on the rob_this line: a child's better state, max(left_rob, left_skip), may be the one where the child is robbed, so a robbed node adds left_skip, never the child's max.
Adding
max(left_rob, left_skip)torob_thisAdding
left_rob + right_robtoskip_thisReturning
dfs(root)[0]instead ofmax(dfs(root))Recursing into grandchildren instead of returning both states
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Binary tree" plus a rule between directly linked nodes ("both ends of an edge") plus "the most money": every node is a yes/no choice, and which choices are allowed depends on the children's choices. That is the signal for Tree State DP: each node returns one best total per state it can be in.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
A robbed node needs both children skipped: rob_this = node.val + left_skip + right_skip. A skipped node lets each child take its better state: skip_this = max(left_rob, left_skip) + max(right_rob, right_skip). The answer is max(dfs(root)).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
rob_thisaddsleft_skip + right_skip, never a child's better state.Call
dfsonce per child and unpack the pair (left_rob, left_skip = dfs(node.left)). Readingdfs(node.left)[1]forrob_thisand callingdfs(node.left)again forskip_thissolves every subtree twice per level: on a chain of 20 houses that is over 4 million calls instead of 41.If you memoize the grandchildren version instead, key the memo by the node itself, never by
node.val: different houses can hold the same amount, and a value key hands one house's answer to another.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Tree State DP. The rule links each house to its parent, so one number per subtree isn't enough: the parent needs to know whether its child was robbed. So my DFS returns two numbers for every node: the best total in its subtree if the node is robbed, and if it is skipped. I compute them in postorder. If I rob the node, both children must be skipped, so rob_this is node.val plus the two children's skip values. If I skip it, each child is free, so skip_this adds the larger of each child's two values. The answer is the larger of the root's two. The trap is robbing a node on top of a child's best total: that best may already rob the child, which breaks the rule. Each node is solved once, so it's
O(N)time and O(H) recursion stack.
Complexity & Mathematical Proof
O(N)
Look at the code: dfs is called once for every node and once for every empty child slot, and a tree with N nodes has N + 1 empty slots, so there are 2N + 1 calls. Each call does O(1) work: two tuple unpacks, one sum for rob_this, and two max calls and one sum for skip_this. No subtree is solved twice, because each call hands both of its states up and the parent reuses them instead of calling dfs on a grandchild. Total: O(N).
O(H) recursion stack
The recursion goes down one level per call, so the call stack holds at most H + 1 frames, where H is the height of the tree: about log N when it is balanced, and N on a chain. Each frame keeps four integers. The answer is one integer.
Derivation Progression
N + (N + 1) = 2N + 1
dfs runs once per node and once per empty child slot, where if not node: return (0, 0) answers at once.
O(1)
Unpack left_rob, left_skip and right_rob, right_skip, add up rob_this, take two max values for skip_this, return the pair.
each subtree solved once
The parent reuses the pair its child returned; it never calls dfs on a grandchild, which is what makes the brute force exponential.
O(N)
2N + 1 calls, O(1) each, then one max at the root.
Variable Definitions
Number of nodes (houses) in the tree
Height of the tree: about log N when balanced, up to N on a chain
Memory Architecture & Bounds
O(H): one frame per level of the current root-to-node path
O(1): each frame keeps four integers, no extra structure
O(1): one integer
Boundary Best / Worst Cases
time and an stack on a balanced tree
time; the stack depth is the tree height
time and an stack on a chain
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "binary tree", "both ends of an edge", "the most money". A yes/no choice at every node plus a rule between a parent and its child: Tree State DP, where each node returns one best total per state it can be in.
nodes and values up to , so any total stays below . Trying every set of houses is ; recursing on grandchildren without saving results is exponential in the height; returning both states is time and an recursion stack.
A chain of houses is calls deep, past the default recursion limit of many runtimes (CPython's is 1000): raise the limit or run the same postorder with an explicit stack. Memoizing rob(node) in a hash map keyed by node also reaches , but pays for an extra map of entries; returning the pair needs no map at all.