Initialize DP Table and Start Post-Order Traversal
We start with an empty DP table for all nodes. No DP values are computed yet, so all cells are '?'. The traversal will process nodes from leaves up to the root.
💡 Initialization sets the stage for bottom-up computation, ensuring no values are assumed before processing children.
Line:def rob(root):
def dfs(node):
if not node:
return (0, 0)
💡 DP values must be computed bottom-up; leaves first, then parents.
fill_cells
Process Leaf Node with Value 3 (Right child of left child)
We reach the leaf node with value 3 (right child of left child). Since it has no children, rob = 3 and not_rob = 0.
💡 Leaf nodes have simple DP values: rob equals node value, not_rob is zero because no children to rob.
Line:if not node:
return (0, 0)
left = dfs(node.left)
right = dfs(node.right)
💡 Leaf nodes provide base cases for DP computation.
fill_cells
Process Leaf Node with Value 1 (Right child of right child)
We process the leaf node with value 1 (right child of right child). Its rob value is 1 and not_rob is 0, as it has no children.
💡 Similar to previous leaf, base DP values are straightforward.
Line:if not node:
return (0, 0)
left = dfs(node.left)
right = dfs(node.right)
💡 Leaf nodes consistently provide base DP values.
fill_cells
Process Node with Value 2 (Left child)
For node 2, rob = 2 + not_rob of children = 2 + 0 + 0 = 2. not_rob = max(rob, not_rob) of children = max(0,3) = 3.
💡 Combining children's DP values shows how robbing this node excludes robbing children.
💡 The root's DP values summarize the entire tree's optimal robbery plan.
compare
Compare rob and not_rob at Root to Find Final Answer
We compare rob (7) and not_rob (6) at the root. Since 7 > 6, the maximum amount robbed is 7.
💡 The final answer is the maximum of rob and not_rob at the root node.
Line:return max(dfs(root))
💡 The final decision is made by comparing the two DP states at the root.
reconstruct
Summary: Robbing Nodes 3 (root), 3 (right child of left child), and 1 (right child of right child)
The optimal solution includes robbing the root (3), the right child of the left child (3), and the right child of the right child (1), totaling 7.
💡 This step connects DP values to actual nodes robbed, clarifying the solution.
Line:# Reconstruction is conceptual here; no explicit code
💡 DP values encode which nodes to rob to maximize money without robbing adjacent nodes.
fill_cells
Confirm DP Table Fully Computed
All nodes have their DP values computed, no '?' remain. The table fully represents the solution space.
💡 Complete DP table ensures no missing computations and correctness of the solution.
Line:return max(dfs(root))
💡 DP table completeness is essential for correctness and final answer extraction.
finalize
Final Step: Return Maximum Robbed Amount
The algorithm returns 7, the maximum amount that can be robbed from the tree without alerting the police.
💡 Returning the max of rob and not_rob at root completes the algorithm.
Line:return max(dfs(root))
💡 The final returned value is the solution to the problem.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob(root):
def dfs(node):
if not node: # STEP 1
return (0, 0) # (not_rob, rob)
left = dfs(node.left) # STEP 2-5
right = dfs(node.right)
rob_node = node.val + left[0] + right[0] # STEP 4
not_rob_node = max(left) + max(right) # STEP 4
return (not_rob_node, rob_node) # STEP 6
return max(dfs(root)) # STEP 7
📊
House Robber III (On Tree) - Watch the Algorithm Execute, Step by Step
Watching the algorithm step-by-step reveals how the tree structure influences the DP decisions and why robbing adjacent nodes is forbidden.
Step 1/10
·Active fill★Answer cell
Initializing dp array
i\w
0
1
i=0
?
?
i=1
?
?
i=2
?
?
i=3
?
?
i=4
?
?
uncomputed
Item 3 - wt:0 val:3
i\w
0
1
i=0
?
?
i=1
?
?
i=2
?
?
i=3
0
3
i=4
?
?
leaf node computed
Item 4 - wt:0 val:1
i\w
0
1
i=0
?
?
i=1
?
?
i=2
?
?
i=3
0
3
i=4
0
1
leaf node computed
Item 1 - wt:0 val:2
i\w
0
1
i=0
?
?
i=1
3
2
i=2
?
?
i=3
0
3
i=4
0
1
node computed
Item 2 - wt:0 val:3
i\w
0
1
i=0
?
?
i=1
3
2
i=2
1
3
i=3
0
3
i=4
0
1
node computed
Item 0 - wt:0 val:3
i\w
0
1
i=0
6
7
i=1
3
2
i=2
1
3
i=3
0
3
i=4
0
1
root computed
Item 0 - wt:0 val:7
i\w
0
1
i=0
6
7
i=1
3
2
i=2
1
3
i=3
0
3
i=4
0
1
final answer
Item 0 - wt:0 val:7
i\w
0
1
i=0
6
7
i=1
3
2
i=2
1
3
i=3
0
3
i=4
0
1
robbed root
Initializing dp array
i\w
0
1
i=0
6
7
i=1
3
2
i=2
1
3
i=3
0
3
i=4
0
1
computed
Item 0 - wt:0 val:7
i\w
0
1
i=0
6
7
i=1
3
2
i=2
1
3
i=3
0
3
i=4
0
1
answer cell
Key Takeaways
✓ DP on trees requires bottom-up post-order traversal to ensure children are processed before parents.
This traversal order is crucial because parent's DP values depend on children's results, which is not obvious from code alone.
✓ Each node stores two DP states: rob and not_rob, representing mutually exclusive choices.
Understanding these two states clarifies why we cannot rob adjacent nodes and how the algorithm enforces this constraint.
✓ The final answer is the max of rob and not_rob at the root, reflecting the best overall choice.
Seeing the final comparison visually helps students grasp how the DP values translate to the solution.
Practice
(1/5)
1. You need to visit all nodes of a binary tree in the order: root node first, then recursively the left subtree, followed by the right subtree. Which algorithmic approach guarantees this traversal order efficiently without extra space for recursion or stack?
easy
A. Postorder traversal using two stacks
B. Level-order traversal using a queue
C. Morris preorder traversal using threaded binary tree
D. Inorder traversal using recursion
Solution
Step 1: Understand traversal order requirement
The problem requires visiting root before left and right subtrees, which is preorder traversal.
Step 2: Identify approach with no extra space
Morris preorder traversal uses threaded binary trees to achieve preorder traversal without recursion or stack, thus optimal in space.
Final Answer:
Option C -> Option C
Quick Check:
Preorder visits root first; Morris traversal achieves this with O(1) space [OK]
Hint: Preorder visits root before children [OK]
Common Mistakes:
Confusing inorder or postorder with preorder traversal
Assuming recursion is always needed
Using level-order which visits nodes by depth
2. Given the following code for inverting a binary tree, what is the value of the left child of the root node after calling invertTree(root) on the tree below?
Tree structure before inversion:
2
/ \
1 3
easy
A. 3
B. 1
C. 2
D. null
Solution
Step 1: Trace recursive calls on root=2
invertTree called on left child (1) and right child (3), both leaves, so their children are null and return immediately.
Step 2: Swap left and right children of root=2
After recursion, root.left and root.right are swapped: left becomes 3, right becomes 1.
Final Answer:
Option A -> Option A
Quick Check:
Root's left child after inversion is original right child 3 [OK]
Hint: Swapping children after recursion flips subtree positions [OK]
Common Mistakes:
Confusing left and right child values after inversion
Forgetting to swap after recursive calls
Assuming root value changes
3. Suppose the problem changes: the binary tree is no longer complete but only a general binary tree. Which of the following statements about counting nodes efficiently is true?
hard
A. Breadth-first search (BFS) can count nodes in O(log n) time for any binary tree.
B. The optimal binary search approach on the last level still applies with minor modifications.
C. Using tree height to check perfect subtrees can still reduce time complexity to O((log n)^2).
D. A simple DFS traversal counting all nodes is the only guaranteed correct method with O(n) time.
Solution
Step 1: Understand the problem change
The tree is no longer complete, so properties used by optimal methods do not hold.
Step 2: Identify correct counting method
Only a full traversal (DFS or BFS) guarantees counting all nodes correctly in O(n) time.
Final Answer:
Option D -> Option D
Quick Check:
Optimal methods rely on completeness, which is lost here [OK]
Hint: Without completeness, must traverse all nodes [OK]
Common Mistakes:
Trying to apply binary search on last level
Assuming height checks still reduce complexity
4. Suppose you want to invert a binary tree where nodes can have an arbitrary number of children (not just two). Which modification to the inversion algorithm correctly generalizes the inversion to this n-ary tree?
hard
A. Swap only the first and last child pointers recursively, leaving others unchanged.
B. Use BFS to swap children pairwise at each level without recursion.
C. Recursively invert each child's subtree, then reverse the list of children in-place.
D. Invert only the leftmost and rightmost subtrees recursively, ignoring middle children.
Solution
Step 1: Understand inversion for binary tree swaps left and right children
For n-ary trees, inversion means reversing the order of children after inverting each child's subtree.
Step 2: Generalize recursion and reversal
Recursively invert each child's subtree, then reverse the children list to mirror the tree structure.
Step 3: Evaluate other options
Swapping only first and last or partial BFS swaps do not fully invert the tree structure.
Final Answer:
Option C -> Option C
Quick Check:
Recursion plus reversing children list generalizes inversion correctly [OK]
Hint: Invert subtrees recursively, then reverse children list for n-ary trees [OK]
Common Mistakes:
Swapping only some children pairs
Ignoring recursion on all children
Using BFS without recursion for full inversion
5. Suppose the problem is modified so that node values can be negative integers, and the goal remains to sum all root-to-leaf numbers formed by concatenation (including negative signs). Which of the following changes to the algorithm is necessary to handle this correctly?
hard
A. Skip negative nodes since they break number formation
B. Continue using integer arithmetic with multiplication by 10, ignoring signs
C. Add absolute values of node.val to current_number to avoid sign issues
D. Use string concatenation of node values along the path and convert to integer at leaf nodes
Solution
Step 1: Understand impact of negative values
Integer arithmetic with multiplication by 10 assumes digits 0-9; negative signs break this assumption.
Step 2: Identify correct approach
Concatenating node values as strings preserves negative signs and digit order; convert to integer only at leaf nodes.
Step 3: Confirm other options fail
Ignoring signs or skipping negatives leads to incorrect sums or incomplete paths.