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. Consider the following code snippet for computing the diameter of a binary tree. Given the tree: root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3)), what is the final value returned by diameterOfBinaryTree(root)?

easy

A. 5

B. 2

C. 4

D. 3

Solution

1. Step 1: Trace height of left subtree rooted at node 2

   Height of node 4 and 5 is 1 each, so height(2) = 1 + max(1,1) = 2. Diameter updated to max(0,1+1)=2.

2. Step 2: Trace height of right subtree rooted at node 3 and root

   Height(3) = 1 (leaf). At root, diameter = max(2, 2 + 1) = 3. Height(root) = 1 + max(2,1) = 3.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Diameter is edges count on longest path 4->2->1->3 = 3 edges [OK]

Hint: Diameter counts edges, not nodes [OK]

Common Mistakes:

• Returning number of nodes instead of edges
• Off-by-one in height calculation

2. You are given an integer array and need to find how many distinct longest strictly increasing subsequences it contains. Which approach guarantees an optimal solution that efficiently counts all such subsequences without enumerating them explicitly?

easy

A. A greedy algorithm that picks the first increasing subsequence found and counts its length

B. A pure recursive backtracking approach that tries all subsequences to count the longest ones

C. Sorting the array and counting increasing subsequences using combinatorial formulas

D. Dynamic programming that tracks length and count of LIS ending at each index with O(n²) time complexity

Solution

1. Step 1: Understand problem requirements

   The problem requires counting all longest increasing subsequences, not just finding one or their length.

2. Step 2: Evaluate approaches

   Greedy fails because it finds only one LIS, recursion is exponential and inefficient, sorting loses original order, but DP with length and count arrays correctly tracks LIS counts in O(n²).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP with length and count arrays is standard for counting LIS [OK]

Hint: DP with length and count arrays counts LIS correctly [OK]

Common Mistakes:

• Assuming greedy finds all LIS
• Thinking sorting helps count LIS
• Using pure recursion without pruning

3. The following code attempts to solve the Russian Doll Envelopes problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes by width ascending and height ascending

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing element in lis at found index

Solution

1. Step 1: Examine sorting order

   Sorting by width ascending and height ascending causes envelopes with same width but increasing height to be counted incorrectly in LIS.

2. Step 2: Understand LIS requirement

   Heights must be sorted descending for equal widths to avoid counting invalid envelopes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting order bug leads to wrong LIS and incorrect nesting count [OK]

Hint: Sort height descending for equal widths to avoid LIS errors [OK]

Common Mistakes:

• Sorting both dimensions ascending instead of height descending
• Misusing bisect functions
• Incorrectly extracting heights

4. Suppose the problem is modified so that caps can be assigned to multiple people (i.e., caps are no longer unique). Which of the following algorithmic changes correctly adapts the solution to count the number of ways to assign caps without uniqueness constraints?

hard

A. Remove bitmask tracking and use simple multiplication of counts per person

B. Keep bitmask DP but allow assigning the same cap multiple times by not checking mask bits

C. Use a DP over persons only, multiplying the number of caps each person can wear

D. Use a nested loop over persons and caps without bitmask, summing ways for each person independently

Solution

1. Step 1: Understand the uniqueness constraint removal

   Without uniqueness, caps can be reused freely, so no need to track assigned caps with bitmasks.

2. Step 2: Simplify counting approach

   Counting ways reduces to multiplying the number of caps each person can wear, as assignments are independent.

3. Step 3: Why other options fail

   Bitmask DP is unnecessary and incorrect if caps can be reused; summing independently without multiplication misses combinations.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing bitmask and multiplying counts per person matches problem relaxation [OK]

Hint: No uniqueness -> no bitmask needed, multiply counts [OK]

Common Mistakes:

• Trying to keep bitmask DP unnecessarily
• Summing instead of multiplying counts

5. Suppose the problem changes: now you want to count the number of longest increasing subsequences where elements can be reused multiple times (i.e., subsequences are non-strictly increasing and elements can appear multiple times). Which modification to the Fenwick tree based algorithm correctly handles this?

hard

A. Change the comparison in Fenwick tree queries to allow equal elements and update counts accordingly

B. Replace Fenwick tree with a segment tree that supports range maximum queries and counts for non-strictly increasing sequences

C. No change needed; the original algorithm already counts sequences with reuse

D. Use the same algorithm but double the counts at each update to account for reuse

Solution

1. Step 1: Understand reuse and non-strictly increasing requirement

   Allowing reuse means subsequences can have equal elements and elements can be chosen multiple times, breaking strict increasing assumption.

2. Step 2: Why Fenwick tree needs modification

   Fenwick tree queries rely on strictly increasing order and unique indices; to handle reuse and non-strict sequences, segment tree with range max and count queries is needed to correctly aggregate counts over ranges including equal elements.

3. Step 3: Evaluate options

   Simply changing comparison or doubling counts is incorrect; original algorithm assumes strict increasing and no reuse.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Segment tree supports flexible queries needed for reuse and non-strict sequences [OK]

Hint: Reuse breaks strict increasing; segment tree needed [OK]

Common Mistakes:

• Assuming original Fenwick tree works
• Trying to double counts naively
• Ignoring non-strict condition