Builds on Bottom-Up DFS and Linear DP, which you haven’t finished yet.
Tree State DP (Return Several States per Node)
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.
Tree State DP
tree node ➔ one best total per state (take / skip) ➔ parent combines the tuples| 1 | from typing import Optional |
| 2 | |
| 3 | class TreeNode: |
| 4 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 5 | self.val = val |
| 6 | self.left = left |
| 7 | self.right = right |
| 8 | |
| 9 | def rob(root: Optional[TreeNode]) -> int: |
| 10 | """House Robber III: most money from a tree of houses, never robbing a parent and |
| 11 | its child. |
| 12 | Time: O(N) | Space: O(H) recursion stack |
| 13 | """ |
| 14 | def dfs(node: Optional[TreeNode]) -> tuple[int, int]: |
| 15 | """(rob_this, skip_this): the best total in node's subtree when node is robbed / |
| 16 | skipped.""" |
| 17 | if not node: |
| 18 | return (0, 0) # An empty subtree earns nothing either way |
| 19 | # Postorder: each child reports both of its states |
| 20 | left_rob, left_skip = dfs(node.left) |
| 21 | right_rob, right_skip = dfs(node.right) |
| 22 | # Robbed: both children must be skipped |
| 23 | rob_this = node.val + left_skip + right_skip |
| 24 | # Skipped: each child takes its better state |
| 25 | skip_this = max(left_rob, left_skip) + max(right_rob, right_skip) |
| 26 | return (rob_this, skip_this) |
| 27 | |
| 28 | return max(dfs(root)) # The root has no parent: take its better state |
dfs(node) returns (rob_this, skip_this): the best total in node's subtree with node robbed and with node skipped, each already obeying the rule everywhere below.One best total per subtree hides whether its root was robbed, and the parent needs exactly that, so let dfs(node) return one best total per state: (rob_this, skip_this). The rule only links a node to its children, so the parent enforces it using the children's states alone: rob_this = node.val + left_skip + right_skip, skip_this = max(left_rob, left_skip) + max(right_rob, right_skip), and the root, which has no parent, takes max(dfs(root)). Each pair is final when it is returned, so every subtree is solved once and nothing below the children is looked at again. The trap is the rob_this line: adding a child's better state, max(left_rob, left_skip), instead of left_skip lets a robbed child sit under a robbed parent, because the better state may be the robbed one.
See it run
Tree state DP: each node returns two totals, step by step
node nonerob_this -skip_this -answer not known yet
Each circle is a house with its money. The row under the tree lists the pair each finished node returned, as the node value and (rob_this, skip_this).
computingthe node whose pair is being made from its children's pairschildrenthe children whose returned pairs are readreturneda node that has already returned its pairanswerthe root, where the answer is the larger total of its pair
dfs asks both children first, so the first pair is made at the deepest left node. A missing node returns (0, 0).
Gotcha 1 of 4
- The trap
Gotcha 1: Adding
max(left_rob, left_skip)torob_thisMistakerob_this = node.val + max(left_rob, left_skip) + max(right_rob, right_skip)Fixrob_this = node.val + left_skip + right_skipWhat happens: When
nodeis robbed, neither child may be robbed. A child's better state,max(left_rob, left_skip), may be the robbed one. Adding it lets a robbed child sit under a robbed parent. Onlyleft_skipandright_skipkeep the rule.Example: House Robber III (LC 337): root = [3,2,3,null,3,null,1]Mistake: returns 12Fix: returns 7
- You look for one best path that may bend at any node, as in Binary Tree Maximum Path Sum (LC 124): no node makes a choice that limits its children, so one returned number, the best leg, is enough. See Tree Diameter DP
- Every node's need is fixed and you minimize what crosses the edges, as in Distribute Coins in Binary Tree (LC 979): there is nothing to choose per node, so a single signed surplus per subtree says it all. See Greedy Tree DP
Deep Dive
Why each node returns two numbers
In House Robber III (LC 337), each house is a node. You cannot rob a house and its child together. A parent needs to know two facts about each child subtree: the best total when the child is robbed, and the best total when the child is skipped. One number cannot say which of the two it is.
So dfs(node) returns the pair (rob_this, skip_this). If node is robbed, both children must be skipped, so rob_this = node.val + left_skip + right_skip. If node is skipped, each child is free, so skip_this = max(left_rob, left_skip) + max(right_rob, right_skip). A missing node returns (0, 0).
Example: root = [3, 4, 5, 1, 3, null, 1]. The two leaves 1 and 3 under 4 return (1, 0) and (3, 0). Then 4 returns (4, 4): robbing 4 gives 4, and skipping 4 gives 1 + 3. The leaf 1 under 5 returns (1, 0), so 5 returns (5, 1). The root 3 gets rob_this = 3 + 4 + 1 = 8 and skip_this = max(4, 4) + max(5, 1) = 9. The answer is max(8, 9) = 9.
The trap: add the skip values, not the better values, to rob_this
The wrong line is rob_this = node.val + max(left_rob, left_skip) + max(right_rob, right_skip). The better state of a child may be the robbed one. Then a robbed child sits under a robbed parent, which the rule forbids.
On root = [3, 2, 3, null, 3, null, 1], the wrong line returns 12. The correct answer is 7. Only left_skip and right_skip keep the rule.
A second fault is skip_this = left_rob + right_rob. It forces both children to be robbed. Sometimes it is best to skip two houses in a row. On [4, 1, null, 2, null, 3], the best is to rob 4 and 3, which gives 7. The wrong line returns 6.
A third fault is return dfs(root)[0]. The root has no parent, so skipping it is allowed. On [3, 4, 5, 1, 3, null, 1], dfs(root)[0] is 8 and the correct answer is max(dfs(root)) = 9.
Why returning a pair solves each node once
Another way compares node.val plus the grandchildren's totals with the children's totals. It calls itself on both the children and the grandchildren, so the same subtree is solved again and again.
Example: count the calls on a chain of nodes, where each node has one left child. With 10 nodes it makes 463 calls, with 20 nodes it makes 57,311 calls, and with 30 nodes it makes 7,049,153 calls. The count was measured by running the code, and it includes calls on missing nodes. The count grows exponentially.
The pair removes the repeated work. Each dfs call returns both states, so the parent never looks at a grandchild. Each node is solved once.
The cost, and the neighbour cards
Each node is visited once and does a constant amount of work, so the time is O(N). The space is O(H) for the recursion, where H is the height of the tree.
The idea is the same as House Robber (LC 198) on a line. There, prev1 and prev2 hold the answers for the last two houses. On a tree, a node has two children and no single previous house, so each node returns its own pair.
Binary Tree Maximum Path Sum (LC 124) is a neighbour. It looks for one best path that may bend at any node. No node makes a choice that limits its children, so one returned number is enough. Distribute Coins in Binary Tree (LC 979) is another neighbour. The need of each node is fixed, so one signed number per subtree is enough.
Binary Tree Cameras (LC 968) has three states per node, and the same method returns a triple.
60-Second Pitch
"One number per subtree cannot tell the parent whether the child was robbed, and the parent needs that. So each call returns two numbers, (rob_this, skip_this). If I rob the node, both children must be skipped, so rob_this = node.val + left_skip + right_skip. If I skip the node, each child takes its better state, so skip_this = max(left_rob, left_skip) + max(right_rob, right_skip). The root has no parent, so the answer is the larger of its two numbers. Each node is solved once, so the time is O(N) and the space is O(H)."
Common Questions
- Why does one number per node not work?
The parent must know if the child was robbed. The best total of a child subtree might come from robbing the child, and then the parent cannot be robbed. If the child returns only the better total, the parent cannot tell the two cases apart. So the child returns one total for each case.
- What are the time and space complexity?
O(N)time, because each node is visited once with constant work. O(H) space for the recursion, where H is the height of the tree. The pair is two integers, so the extra space per call is constant.- Why
max(dfs(root))and notdfs(root)[0]? dfs(root)[0]is the best total when the root is robbed. The root has no parent, so skipping it is allowed. On[3, 4, 5, 1, 3, null, 1],dfs(root)[0]is 8 and the correct answer is 9.- How is it different from House Robber (LC 198)?
- How would you change it when a node has three states?
Return a tuple with one entry per state and write one formula per state from the children's tuples. Binary Tree Cameras (LC 968) does this. The time is still
O(N), because each node is solved once, and each formula uses only the node's own children.
SWE Reasoning
Spot it
- Each tree node is a choice: take it or skip it, cover it or not.
- A rule links a node to its children, such as "no two linked nodes are both taken".
- The goal is a best total (maximum or minimum) for the whole tree.
- One number per subtree is not enough, because the parent also needs to know the choice made at the root of that subtree.
- The wording has "adjacent", "directly linked", "cannot both" or "covered".
The invariant, step by step
dfs(node)returns(rob_this, skip_this): the best total in the subtree ofnodewhennodeis robbed, and whennodeis skipped.- A missing node returns
(0, 0), because an empty subtree earns nothing. - The call first asks both children, so
left_rob,left_skip,right_robandright_skipare known. Each pair is final and obeys the rule everywhere below. - If
nodeis robbed, neither child may be robbed, sorob_this = node.val + left_skip + right_skip. - If
nodeis skipped, each child picks its better state, soskip_this = max(left_rob, left_skip) + max(right_rob, right_skip). - The root has no parent, so the answer is
max(dfs(root)).
Traps
max(left_rob, left_skip)insiderob_this. A robbed child can sit under a robbed parent. Useleft_skipandright_skip.left_rob + right_robforskip_this. It forces both children to be robbed. Use the better state of each child.dfs(root)[0]as the answer. It forgets that the root may be skipped. Usemax(dfs(root)).- Recursing into grandchildren. Without stored results, the same subtree is solved again and again, and the time is exponential. Return the pair.
- Wrong value for a missing node. It must be
(0, 0), notNone.
Practice
Builds on Bottom-Up DFS and Linear DP, which you haven’t finished yet.
Tree State DP (Return Several States per Node)
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.
Tree State DP
tree node ➔ one best total per state (take / skip) ➔ parent combines the tuples| 1 | from typing import Optional |
| 2 | |
| 3 | class TreeNode: |
| 4 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 5 | self.val = val |
| 6 | self.left = left |
| 7 | self.right = right |
| 8 | |
| 9 | def rob(root: Optional[TreeNode]) -> int: |
| 10 | """House Robber III: most money from a tree of houses, never robbing a parent and |
| 11 | its child. |
| 12 | Time: O(N) | Space: O(H) recursion stack |
| 13 | """ |
| 14 | def dfs(node: Optional[TreeNode]) -> tuple[int, int]: |
| 15 | """(rob_this, skip_this): the best total in node's subtree when node is robbed / |
| 16 | skipped.""" |
| 17 | if not node: |
| 18 | return (0, 0) # An empty subtree earns nothing either way |
| 19 | # Postorder: each child reports both of its states |
| 20 | left_rob, left_skip = dfs(node.left) |
| 21 | right_rob, right_skip = dfs(node.right) |
| 22 | # Robbed: both children must be skipped |
| 23 | rob_this = node.val + left_skip + right_skip |
| 24 | # Skipped: each child takes its better state |
| 25 | skip_this = max(left_rob, left_skip) + max(right_rob, right_skip) |
| 26 | return (rob_this, skip_this) |
| 27 | |
| 28 | return max(dfs(root)) # The root has no parent: take its better state |
dfs(node) returns (rob_this, skip_this): the best total in node's subtree with node robbed and with node skipped, each already obeying the rule everywhere below.One best total per subtree hides whether its root was robbed, and the parent needs exactly that, so let dfs(node) return one best total per state: (rob_this, skip_this). The rule only links a node to its children, so the parent enforces it using the children's states alone: rob_this = node.val + left_skip + right_skip, skip_this = max(left_rob, left_skip) + max(right_rob, right_skip), and the root, which has no parent, takes max(dfs(root)). Each pair is final when it is returned, so every subtree is solved once and nothing below the children is looked at again. The trap is the rob_this line: adding a child's better state, max(left_rob, left_skip), instead of left_skip lets a robbed child sit under a robbed parent, because the better state may be the robbed one.
See it run
Tree state DP: each node returns two totals, step by step
node nonerob_this -skip_this -answer not known yet
Each circle is a house with its money. The row under the tree lists the pair each finished node returned, as the node value and (rob_this, skip_this).
computingthe node whose pair is being made from its children's pairschildrenthe children whose returned pairs are readreturneda node that has already returned its pairanswerthe root, where the answer is the larger total of its pair
dfs asks both children first, so the first pair is made at the deepest left node. A missing node returns (0, 0).
Gotcha 1 of 4
- The trap
Gotcha 1: Adding
max(left_rob, left_skip)torob_thisMistakerob_this = node.val + max(left_rob, left_skip) + max(right_rob, right_skip)Fixrob_this = node.val + left_skip + right_skipWhat happens: When
nodeis robbed, neither child may be robbed. A child's better state,max(left_rob, left_skip), may be the robbed one. Adding it lets a robbed child sit under a robbed parent. Onlyleft_skipandright_skipkeep the rule.Example: House Robber III (LC 337): root = [3,2,3,null,3,null,1]Mistake: returns 12Fix: returns 7
- You look for one best path that may bend at any node, as in Binary Tree Maximum Path Sum (LC 124): no node makes a choice that limits its children, so one returned number, the best leg, is enough. See Tree Diameter DP
- Every node's need is fixed and you minimize what crosses the edges, as in Distribute Coins in Binary Tree (LC 979): there is nothing to choose per node, so a single signed surplus per subtree says it all. See Greedy Tree DP
Deep Dive
Why each node returns two numbers
In House Robber III (LC 337), each house is a node. You cannot rob a house and its child together. A parent needs to know two facts about each child subtree: the best total when the child is robbed, and the best total when the child is skipped. One number cannot say which of the two it is.
So dfs(node) returns the pair (rob_this, skip_this). If node is robbed, both children must be skipped, so rob_this = node.val + left_skip + right_skip. If node is skipped, each child is free, so skip_this = max(left_rob, left_skip) + max(right_rob, right_skip). A missing node returns (0, 0).
Example: root = [3, 4, 5, 1, 3, null, 1]. The two leaves 1 and 3 under 4 return (1, 0) and (3, 0). Then 4 returns (4, 4): robbing 4 gives 4, and skipping 4 gives 1 + 3. The leaf 1 under 5 returns (1, 0), so 5 returns (5, 1). The root 3 gets rob_this = 3 + 4 + 1 = 8 and skip_this = max(4, 4) + max(5, 1) = 9. The answer is max(8, 9) = 9.
The trap: add the skip values, not the better values, to rob_this
The wrong line is rob_this = node.val + max(left_rob, left_skip) + max(right_rob, right_skip). The better state of a child may be the robbed one. Then a robbed child sits under a robbed parent, which the rule forbids.
On root = [3, 2, 3, null, 3, null, 1], the wrong line returns 12. The correct answer is 7. Only left_skip and right_skip keep the rule.
A second fault is skip_this = left_rob + right_rob. It forces both children to be robbed. Sometimes it is best to skip two houses in a row. On [4, 1, null, 2, null, 3], the best is to rob 4 and 3, which gives 7. The wrong line returns 6.
A third fault is return dfs(root)[0]. The root has no parent, so skipping it is allowed. On [3, 4, 5, 1, 3, null, 1], dfs(root)[0] is 8 and the correct answer is max(dfs(root)) = 9.
Why returning a pair solves each node once
Another way compares node.val plus the grandchildren's totals with the children's totals. It calls itself on both the children and the grandchildren, so the same subtree is solved again and again.
Example: count the calls on a chain of nodes, where each node has one left child. With 10 nodes it makes 463 calls, with 20 nodes it makes 57,311 calls, and with 30 nodes it makes 7,049,153 calls. The count was measured by running the code, and it includes calls on missing nodes. The count grows exponentially.
The pair removes the repeated work. Each dfs call returns both states, so the parent never looks at a grandchild. Each node is solved once.
The cost, and the neighbour cards
Each node is visited once and does a constant amount of work, so the time is O(N). The space is O(H) for the recursion, where H is the height of the tree.
The idea is the same as House Robber (LC 198) on a line. There, prev1 and prev2 hold the answers for the last two houses. On a tree, a node has two children and no single previous house, so each node returns its own pair.
Binary Tree Maximum Path Sum (LC 124) is a neighbour. It looks for one best path that may bend at any node. No node makes a choice that limits its children, so one returned number is enough. Distribute Coins in Binary Tree (LC 979) is another neighbour. The need of each node is fixed, so one signed number per subtree is enough.
Binary Tree Cameras (LC 968) has three states per node, and the same method returns a triple.
60-Second Pitch
"One number per subtree cannot tell the parent whether the child was robbed, and the parent needs that. So each call returns two numbers, (rob_this, skip_this). If I rob the node, both children must be skipped, so rob_this = node.val + left_skip + right_skip. If I skip the node, each child takes its better state, so skip_this = max(left_rob, left_skip) + max(right_rob, right_skip). The root has no parent, so the answer is the larger of its two numbers. Each node is solved once, so the time is O(N) and the space is O(H)."
Common Questions
- Why does one number per node not work?
The parent must know if the child was robbed. The best total of a child subtree might come from robbing the child, and then the parent cannot be robbed. If the child returns only the better total, the parent cannot tell the two cases apart. So the child returns one total for each case.
- What are the time and space complexity?
O(N)time, because each node is visited once with constant work. O(H) space for the recursion, where H is the height of the tree. The pair is two integers, so the extra space per call is constant.- Why
max(dfs(root))and notdfs(root)[0]? dfs(root)[0]is the best total when the root is robbed. The root has no parent, so skipping it is allowed. On[3, 4, 5, 1, 3, null, 1],dfs(root)[0]is 8 and the correct answer is 9.- How is it different from House Robber (LC 198)?
- How would you change it when a node has three states?
Return a tuple with one entry per state and write one formula per state from the children's tuples. Binary Tree Cameras (LC 968) does this. The time is still
O(N), because each node is solved once, and each formula uses only the node's own children.
SWE Reasoning
Spot it
- Each tree node is a choice: take it or skip it, cover it or not.
- A rule links a node to its children, such as "no two linked nodes are both taken".
- The goal is a best total (maximum or minimum) for the whole tree.
- One number per subtree is not enough, because the parent also needs to know the choice made at the root of that subtree.
- The wording has "adjacent", "directly linked", "cannot both" or "covered".
The invariant, step by step
dfs(node)returns(rob_this, skip_this): the best total in the subtree ofnodewhennodeis robbed, and whennodeis skipped.- A missing node returns
(0, 0), because an empty subtree earns nothing. - The call first asks both children, so
left_rob,left_skip,right_robandright_skipare known. Each pair is final and obeys the rule everywhere below. - If
nodeis robbed, neither child may be robbed, sorob_this = node.val + left_skip + right_skip. - If
nodeis skipped, each child picks its better state, soskip_this = max(left_rob, left_skip) + max(right_rob, right_skip). - The root has no parent, so the answer is
max(dfs(root)).
Traps
max(left_rob, left_skip)insiderob_this. A robbed child can sit under a robbed parent. Useleft_skipandright_skip.left_rob + right_robforskip_this. It forces both children to be robbed. Use the better state of each child.dfs(root)[0]as the answer. It forgets that the root may be skipped. Usemax(dfs(root)).- Recursing into grandchildren. Without stored results, the same subtree is solved again and again, and the time is exponential. Return the pair.
- Wrong value for a missing node. It must be
(0, 0), notNone.