House Robber III (On Tree)

▶

Steps

setup

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.

Line:

left = dfs(node.left)
right = dfs(node.right)
rob_node = node.val + left[0] + right[0]
not_rob_node = max(left) + max(right)

💡 Robbing a node adds its value plus not robbing children; not robbing node allows robbing or not robbing children for max gain.

fill_cells

Process Node with Value 3 (Right child)

For node 3 (right child), rob = 3 + not_rob of children = 3 + 0 + 0 = 3. not_rob = max(rob, not_rob) of children = max(0,1) = 1.

💡 Same logic applies: robbing node excludes robbing children, not robbing node allows max of children.

Line:

left = dfs(node.left)
right = dfs(node.right)
rob_node = node.val + left[0] + right[0]
not_rob_node = max(left) + max(right)

💡 DP values reflect the best choice at this subtree.

fill_cells

Process Root Node with Value 3

For root node 3, rob = 3 + not_rob of children = 3 + 3 + 1 = 7. not_rob = max(rob, not_rob) of children = 3 + 3 = 6.

💡 Combining children's DP values at root shows maximum money robbable without alerting police.

Line:

rob_node = node.val + left[0] + right[0]
not_rob_node = max(left) + max(right)
return (not_rob_node, rob_node)

💡 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.

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. Given the following code for the optimal camera placement, what is the final number of cameras placed for the tree with root node 0, left child 1, and right child 2 (both children are leaves)?

easy

A. 2

B. 0

C. 3

D. 1

Solution

1. Step 1: Trace dfs on leaf nodes 1 and 2

   Leaves return NOT_COVERED (0) because their children are null and return COVERED_NO_CAM (1). So dfs(1) and dfs(2) return NOT_COVERED.

2. Step 2: At root node 0, left or right child is NOT_COVERED, so place a camera here

   Increment cameras to 1 and return HAS_CAM (2). The root is covered, so no extra camera needed.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   One camera at root covers all nodes [OK]

Hint: Leaves uncovered -> camera at parent -> minimal cameras [OK]

Common Mistakes:

• Counting cameras on leaves instead of parent
• Forgetting to add camera at root if uncovered
• Misinterpreting coverage states

2. What is the time complexity of the brute force approach that separately computes height for each node to check if a binary tree is balanced?

medium

A. O(n^2)

B. O(n)

C. O(n log n)

D. O(n h) where h is tree height

Solution

1. Step 1: Analyze height computation calls

   Height is computed recursively for each node, and each height call traverses subtree nodes.

2. Step 2: Calculate total calls

   For n nodes, height is called at each node, and each call can take O(n) in worst case, leading to O(n^2) total time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Repeated height calls cause quadratic time [OK]

Hint: Repeated height calls cause O(n²) time [OK]

Common Mistakes:

• Assuming height calls are O(1) leading to O(n) time
• Confusing height with depth or tree height h
• Thinking O(n log n) due to balanced tree assumption

3. What is the time complexity of the BFS-based algorithm to compute the maximum depth of a binary tree with n nodes, and why might the following common misconception be incorrect? Options:

medium

A. O(n), but with O(n) auxiliary space for the queue at the widest level

B. O(n), because each node is visited exactly once in BFS

C. O(n log n), because each level requires sorting nodes

D. O(n^2), because each node is enqueued and dequeued multiple times

Solution

1. Step 1: Identify time complexity

   BFS visits each node exactly once, so time complexity is O(n).

2. Step 2: Identify space complexity and common misconception

   Queue can hold up to O(n) nodes at the widest level, so auxiliary space is O(n). The misconception is thinking nodes are processed multiple times, leading to O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each node enqueued and dequeued once; max queue size O(n) [OK]

Hint: BFS visits each node once; space depends on max level width [OK]

Common Mistakes:

• Assuming multiple visits per node
• Confusing sorting with traversal
• Ignoring queue space usage

4. Suppose you want to perform a preorder traversal on a binary tree where nodes can have parent pointers but no left or right pointers. Which approach correctly adapts preorder traversal to this scenario without extra space?

hard

A. Use a modified iterative approach that tracks previously visited nodes to avoid revisiting

B. Use recursion on parent pointers to simulate traversal

C. Iteratively traverse using parent pointers and a stack to track visited nodes

D. Use Morris traversal by creating temporary threaded links on parent pointers

Solution

1. Step 1: Understand traversal constraints

   Without left/right pointers, standard Morris or recursion is not applicable; parent pointers only allow upward traversal.

2. Step 2: Identify correct approach

   Tracking previously visited nodes iteratively allows preorder traversal by moving up/down without extra space for recursion stack.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Modified iterative approach handles parent-only trees without extra space [OK]

Hint: Parent-only trees require tracking visited nodes iteratively [OK]

Common Mistakes:

• Trying to use recursion without child pointers
• Attempting Morris traversal on parent pointers
• Using stack without tracking visited nodes

5. Suppose you want to extend the serialization/deserialization to support binary trees where nodes can have duplicate values and the tree can be very deep (height > 10,000). Which modification is necessary to ensure correctness and efficiency?

hard

A. Use iterative BFS serialization with null markers and iterative deserialization to avoid recursion stack overflow.

B. Use recursive DFS with memoization to handle duplicates and deep trees efficiently.

C. Switch to preorder traversal without null markers to reduce string size and recursion depth.

D. Serialize only unique node values and reconstruct tree assuming balanced shape.

Solution

1. Step 1: Identify problem with deep recursion

   Recursive DFS can cause stack overflow on very deep trees.

2. Step 2: Use iterative BFS with null markers

   Iterative BFS avoids recursion stack issues and null markers preserve structure even with duplicates.

3. Step 3: Avoid assumptions about uniqueness or balanced shape

   Duplicates require storing all nodes explicitly; balanced assumptions break correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Iterative BFS with null markers handles deep trees and duplicates safely [OK]

Hint: Iterative BFS avoids recursion limits and preserves structure [OK]

Common Mistakes:

• Removing null markers to save space breaks reconstruction
• Using recursion on deep trees causes stack overflow
• Assuming unique values or balanced trees