House Robber III (LeetCode 337)
You will see how returning two states per node, robbed and skipped, lets each parent apply the no-parent-and-child rule on its own.
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
Why It Works & Core Invariant
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.
Subproblems & Recurrence Decomposition3 Phases
Because House 1 and House N are adjacent, robbing both is illegal. Decouple the circular graph into two independent linear subproblems: House 0 to N-2 (exclude last) and House 1 to N-1 (exclude first).
# Decouple into two linear runs
loot_1 = rob_linear(nums[:-1]) # Exclude last house
loot_2 = rob_linear(nums[1:]) # Exclude first house
return max(loot_1, loot_2)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. |
Target: House Robber III (LeetCode 337). `(rob_this, skip_this)`: one number could not tell the parent whether the child was robbed.
Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.
Base case: if not node: return base; recursive calls on left/right child nodes.
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.
🪄 The Mathematical Harmony / Magic Trick
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) return max(dfs(root)) 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.
💡 Summary
Return (rob_this, skip_this) from every node in postorder: robbed means node.val plus both children's skip states; skipped means each child's better state. The root takes the max of its two. Every node is solved once: time and recursion stack.
Robbing on top of a child's best:
rob_this = node.val + left_skip + right_skip. Addingmax(left_rob, left_skip)instead lets a robbed child sit under a robbed parent; on[3,2,3,null,3,null,1]it returns 12 instead of 7.Forcing the children of a skipped node:
skip_thisaddsmax(left_rob, left_skip) + max(right_rob, right_skip). Addingleft_rob + right_robmisses two skipped houses in a row ([4,1,null,2,null,3]is 7, not 6).Returning the root's rob state: return
max(dfs(root)). The root has no parent, so skipping it is allowed ([3,4,5,1,3,null,1]is 9, not 8).Recursing on grandchildren without saving results:
max(node.val + rob(grandchildren), rob(children))solves the same subtrees again and again, exponential in the height; returning both states solves each node once.
4-Phase Thought Process Model
You will see how a senior engineer spots a per-node choice with a parent-child rule and answers it with two states per node.
Pattern Recognition Signals
The 10-second spot
"Binary tree" plus a rule between directly linked nodes ("never break into a parent and its child") 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
dfs(node) returns (rob_this, skip_this), the best total in node's subtree when node is robbed and when it is skipped. 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
rob_thisaddsleft_skip + right_skip, nevermax(left_rob, left_skip): a child's better state may be its robbed state, and on[3,2,3,null,3,null,1]taking it returns 12 instead of 7.skip_thisaddsmax(left_rob, left_skip), notleft_rob: two skipped houses in a row can be best, as in[4,1,null,2,null,3], where robbing 4 and 3 gives 7.Return
max(dfs(root)), notdfs(root)[0]: the root has no parent, and on[3,4,5,1,3,null,1]the best total, 9, skips it.Don't recurse on grandchildren without saving results (
max(node.val + rob(grandchildren), rob(children))): the same subtrees are solved again and again, exponential in the height. Returning both states solves each node once.
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.
So: return (rob_this, skip_this); rob_this adds the children's skip states, skip_this each child's better state, and the root takes the max.
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.
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).
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", "never break into two houses joined by 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.
Core Algorithmic State Invariants
`dfs(node)` returns `(rob_this, skip_this)`: the best total in the subtree when `node` is robbed and when it is skipped. One number could not tell the parent which of the two it got.
`rob_this = node.val + left_skip + right_skip`. Adding a child's better state, `max(left_rob, left_skip)`, instead would let a robbed child sit under a robbed parent.
Postorder hands both states up, so a parent never looks below its children: O(N) time and an O(H) recursion stack.
House Robber III (LeetCode 337)
You will see how returning two states per node, robbed and skipped, lets each parent apply the no-parent-and-child rule on its own.
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
Why It Works & Core Invariant
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.
Subproblems & Recurrence Decomposition3 Phases
Because House 1 and House N are adjacent, robbing both is illegal. Decouple the circular graph into two independent linear subproblems: House 0 to N-2 (exclude last) and House 1 to N-1 (exclude first).
# Decouple into two linear runs
loot_1 = rob_linear(nums[:-1]) # Exclude last house
loot_2 = rob_linear(nums[1:]) # Exclude first house
return max(loot_1, loot_2)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. |
Target: House Robber III (LeetCode 337). `(rob_this, skip_this)`: one number could not tell the parent whether the child was robbed.
Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.
Base case: if not node: return base; recursive calls on left/right child nodes.
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.
🪄 The Mathematical Harmony / Magic Trick
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) return max(dfs(root)) 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.
💡 Summary
Return (rob_this, skip_this) from every node in postorder: robbed means node.val plus both children's skip states; skipped means each child's better state. The root takes the max of its two. Every node is solved once: time and recursion stack.
Robbing on top of a child's best:
rob_this = node.val + left_skip + right_skip. Addingmax(left_rob, left_skip)instead lets a robbed child sit under a robbed parent; on[3,2,3,null,3,null,1]it returns 12 instead of 7.Forcing the children of a skipped node:
skip_thisaddsmax(left_rob, left_skip) + max(right_rob, right_skip). Addingleft_rob + right_robmisses two skipped houses in a row ([4,1,null,2,null,3]is 7, not 6).Returning the root's rob state: return
max(dfs(root)). The root has no parent, so skipping it is allowed ([3,4,5,1,3,null,1]is 9, not 8).Recursing on grandchildren without saving results:
max(node.val + rob(grandchildren), rob(children))solves the same subtrees again and again, exponential in the height; returning both states solves each node once.
4-Phase Thought Process Model
You will see how a senior engineer spots a per-node choice with a parent-child rule and answers it with two states per node.
Pattern Recognition Signals
The 10-second spot
"Binary tree" plus a rule between directly linked nodes ("never break into a parent and its child") 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
dfs(node) returns (rob_this, skip_this), the best total in node's subtree when node is robbed and when it is skipped. 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
rob_thisaddsleft_skip + right_skip, nevermax(left_rob, left_skip): a child's better state may be its robbed state, and on[3,2,3,null,3,null,1]taking it returns 12 instead of 7.skip_thisaddsmax(left_rob, left_skip), notleft_rob: two skipped houses in a row can be best, as in[4,1,null,2,null,3], where robbing 4 and 3 gives 7.Return
max(dfs(root)), notdfs(root)[0]: the root has no parent, and on[3,4,5,1,3,null,1]the best total, 9, skips it.Don't recurse on grandchildren without saving results (
max(node.val + rob(grandchildren), rob(children))): the same subtrees are solved again and again, exponential in the height. Returning both states solves each node once.
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.
So: return (rob_this, skip_this); rob_this adds the children's skip states, skip_this each child's better state, and the root takes the max.
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.
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).
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", "never break into two houses joined by 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.
Core Algorithmic State Invariants
`dfs(node)` returns `(rob_this, skip_this)`: the best total in the subtree when `node` is robbed and when it is skipped. One number could not tell the parent which of the two it got.
`rob_this = node.val + left_skip + right_skip`. Adding a child's better state, `max(left_rob, left_skip)`, instead would let a robbed child sit under a robbed parent.
Postorder hands both states up, so a parent never looks below its children: O(N) time and an O(H) recursion stack.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| One best total per state of the node | def dfs(node: Optional[TreeNode]) -> tuple[int, int]: | `(rob_this, skip_this)`: one number could not tell the parent whether the child was robbed. |
| Empty subtree | if not node:
return (0, 0) | No house, no money, whichever state its missing root is in. |
| Children report both states first (postorder) | left_rob, left_skip = dfs(node.left)
right_rob, right_skip = dfs(node.right) | Each pair is already the best for that child's whole subtree; nothing below the children is looked at again. |
| Robbed node: children skipped (the trap) | rob_this = node.val + left_skip + right_skip | A child's better state may be its robbed state, so a robbed node must add the skip states, never `max(left_rob, left_skip)`. |
| Skipped node: each child takes its better state | skip_this = max(left_rob, left_skip) + max(right_rob, right_skip) | Nothing forbids a child either way, so two skipped houses in a row are allowed. |
| Hand both states up | return (rob_this, skip_this) | The parent applies the rule; this node only reports. |
| The root picks its better state | return max(dfs(root)) | The root has no parent, so both of its states are allowed. |