House Robber III (On Tree)

📋

House Robber III (On Tree)

Edge cases:

</>

IDE

def rob(root: Optional[TreeNode]) -> int:public int rob(TreeNode root)int rob(TreeNode* root)function rob(root)

def rob(root):
    # Write your solution here
    pass

class Solution {
    public int rob(TreeNode root) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int rob(TreeNode* root) {
    // Write your solution here
    return 0;
}

function rob(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Sum of all nodes including adjacent nodesFailing to exclude immediate children when robbing a node (no include-exclude logic).✅ Implement DP that adds grandchildren values when including a node and excludes children.

Wrong: Zero for single node treeMissing base case for single node returning node.val.✅ Return node.val if node has no children.

Wrong: Non-zero for empty treeNot checking for null root and returning 0.✅ Return 0 if root is null.

Wrong: TLE on large inputUsing pure recursion without memoization causing exponential time.✅ Add memoization or bottom-up DP to achieve O(n) time.

Wrong: Less than optimal sum due to greedy pickingGreedy approach picking max child instead of DP include-exclude.✅ Use DP to consider both including and excluding nodes with memoization.

✓

Test Cases

Focus on handling base cases and empty inputs correctly.

Watch out for greedy traps and ensure memoization to avoid recomputation.

Optimize your solution to linear time using DP on trees to pass performance tests.

t1_01basic

Input{"root":[3,2,3,null,3,null,1]}

Expected7

⏱ Performance - must finish in 2000ms

Rob houses with values 3 (root), 3 (right child of left child), and 1 (right child of right child). Total = 3 + 3 + 1 = 7.

💡 Think about robbing a node and skipping its immediate children.

💡 Use recursion with memoization to store max values for subtrees.

💡 Calculate max by choosing to rob current node plus grandchildren or skip current node and rob children.

Why it failed: Incorrect output means the solution likely does not correctly exclude immediate children when robbing a node. Fix by ensuring when robbing a node, add grandchildren's values, not children.

✓ Correctly handles the include-exclude logic on tree nodes.

t1_02basic

Input{"root":[3,4,5,1,3,null,1]}

Expected9

⏱ Performance - must finish in 2000ms

Rob houses with values 4 (left child), 5 (right child), and 1 (left child of left child). Total = 4 + 5 + 1 = 9.

💡 Consider both robbing and skipping each node to maximize total.

💡 Use post-order traversal to compute max values bottom-up.

💡 Include current node plus grandchildren or exclude current node and sum children.

Why it failed: If output is less than 9, the solution likely misses adding grandchildren when robbing a node. Fix by adding grandchildren values when including a node.

✓ Correctly computes max robbery amount considering grandchildren.

t2_01edge

Input{"root":null}

Expected0

⏱ Performance - must finish in 2000ms

Empty tree means no houses to rob, so max amount is 0.

💡 Check if the root is null before processing.

💡 Return 0 immediately if tree is empty.

💡 Handle base case of empty input to avoid null pointer errors.

Why it failed: Returning non-zero or error on empty tree means missing null root check. Fix by returning 0 if root is null.

✓ Correctly handles empty tree input.

t2_02edge

Input{"root":[10]}

Expected10

⏱ Performance - must finish in 2000ms

Single node tree, max amount is the node's value itself.

💡 For a single node, robbing it is always optimal.

💡 Base case: return node's value if no children.

💡 Ensure base case returns node.val when no children exist.

Why it failed: If output is 0 or incorrect, base case for single node is missing. Fix by returning node.val when node has no children.

✓ Correctly returns single node value.

t2_03edge

Input{"root":[0,0,0,0,0,0,0]}

Expected0

⏱ Performance - must finish in 2000ms

All nodes have zero value, so max amount robbed is 0.

💡 Check that zero values do not cause incorrect sums.

💡 Ensure max calculation handles zero values correctly.

💡 Verify that including or excluding nodes with zero value returns 0.

Why it failed: If output is non-zero, solution incorrectly sums zero values or has initialization bugs. Fix by proper max comparisons including zero values.

✓ Correctly handles all zero-value nodes.

t2_04edge

Input{"root":[1,null,2,null,3,null,4]}

Expected6

⏱ Performance - must finish in 2000ms

Linear tree with increasing values; optimal to rob nodes 2 and 4 for total 6.

💡 Linear trees behave like House Robber I problem.

💡 Check that solution does not rob adjacent nodes.

💡 Use DP to skip immediate children and include grandchildren.

Why it failed: If output is 10 (sum of all nodes), solution fails to exclude adjacent nodes. Fix by enforcing no two adjacent nodes are robbed.

✓ Correctly handles linear tree with no adjacent robberies.

t3_01corner

Input{"root":[2,null,3,null,4,null,5]}

Expected9

⏱ Performance - must finish in 2000ms

Linear tree (like linked list): rob nodes 2, 4, 5 or 3, 5. Max is 9 by robbing 2,4,5.

💡 Linear trees behave like House Robber I problem.

💡 Check that solution does not greedily pick adjacent nodes.

💡 Use DP to skip immediate children and include grandchildren.

Why it failed: If output is 14 (sum of all nodes), solution fails to exclude adjacent nodes. Fix by enforcing no two adjacent nodes are robbed.

✓ Correctly handles linear tree with no adjacent robberies.

t3_02corner

Input{"root":[4,1,5,2,null,null,1]}

Expected10

⏱ Performance - must finish in 2000ms

Greedy approach fails here; optimal is robbing 4 + 5 + 1 = 10, not just picking max child.

💡 Greedy picking max child value fails on trees.

💡 Use DP to consider both including and excluding nodes.

💡 Calculate max of robbing current node plus grandchildren or children only.

Why it failed: If output is 7, solution uses greedy child picking. Fix by implementing DP with include-exclude logic on tree nodes.

✓ Correctly avoids greedy trap by DP.

t3_03corner

Input{"root":[3,2,3,null,3,null,1]}

Expected7

⏱ Performance - must finish in 2000ms

Test to catch confusion between 0/1 and unbounded knapsack logic on tree nodes.

💡 Each node can be robbed at most once (0/1 constraint).

💡 Do not sum values multiple times for same node.

💡 Use memoization to avoid recomputing subtrees.

Why it failed: If output is greater than 7, solution likely counts nodes multiple times (unbounded). Fix by ensuring each node is counted once with memoization.

✓ Correctly enforces 0/1 constraint on nodes.

t4_01performance

Input{"root":[1,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1],"right":null}

Expectednull

⏱ Performance - must finish in 2000ms

Linear tree with n=100 nodes, O(n) DP must complete within 2 seconds.

💡 Use memoization or bottom-up DP to achieve O(n) time complexity.

Why it failed: TLE indicates exponential brute force recursion without memoization. Fix by adding memoization or bottom-up DP.

✓ Solution runs in O(n) time using DP on trees.

Practice

1. Consider the following iterative postorder traversal code snippet for computing the maximum path sum in a binary tree. Given the tree: 1 / \ 2 3 What is the final value of max_sum after the algorithm completes?

easy

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Trace gains for leaf nodes

   Node 2 and Node 3 are leaves, so gains[2] = 2, gains[3] = 3, max_sum updated to max(-inf, 2) = 2, then max(2,3) = 3.

2. Step 2: Compute gains for root node 1

   left_gain = max(gains[2],0) = 2, right_gain = max(gains[3],0) = 3, price_newpath = 1 + 2 + 3 = 6, max_sum updated to max(3,6) = 6.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of path 2 -> 1 -> 3 is 6 [OK]

Hint: Sum path through root includes both children gains [OK]

Common Mistakes:

• Forgetting to add both children
• Using only max child gain
• Off-by-one in stack processing

2. You are given an undirected graph with n nodes. The task is to find the shortest path length that visits every node at least once. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A bottom-up dynamic programming approach using bitmasking to represent visited nodes and states.

B. A depth-first search (DFS) that explores all permutations of node visits without memoization.

C. A simple breadth-first search (BFS) without tracking visited subsets of nodes.

D. A greedy algorithm that always moves to the nearest unvisited node until all nodes are visited.

Solution

1. Step 1: Understand the problem constraints

   The problem requires visiting all nodes with the shortest path, which is a variant of the Traveling Salesman Problem (TSP) on a graph.

2. Step 2: Identify the suitable algorithmic pattern

   Greedy or simple BFS/DFS without tracking visited subsets cannot guarantee optimality or efficiency. Bitmask DP efficiently encodes visited nodes and uses state transitions to find the shortest path.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask DP is the classic approach for shortest path visiting all nodes [OK]

Hint: Bitmask DP tracks visited subsets optimally [OK]

Common Mistakes:

• Assuming greedy is optimal
• Ignoring visited subsets in BFS
• Trying DFS without memoization

3. What is the time complexity of the optimal greedy solution that sorts pairs by their end values and then iterates through them once to find the longest chain?

medium

A. O(n log n)

B. O(n²)

C. O(n)

D. O(n log n + n²)

Solution

1. Step 1: Identify sorting cost

   Sorting pairs by end values takes O(n log n) time.

2. Step 2: Identify iteration cost

   Iterating through sorted pairs once is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Dominant cost is sorting -> O(n log n) [OK]

Hint: Sorting dominates, iteration is linear [OK]

Common Mistakes:

• Assuming iteration is O(n²) due to nested loops
• Confusing DP approach complexity with greedy
• Ignoring sorting cost

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

5. Suppose the problem is modified so that you can revisit cells multiple times (cycles allowed) and the path must be strictly increasing. Which approach correctly handles this variant without infinite loops?

hard

A. Use DFS with memoization and cycle detection to avoid infinite loops

B. Use topological sort based DP after detecting and removing cycles

C. Use BFS ignoring value order to find longest path

D. Use DFS without memoization to explore all paths

Solution

1. Step 1: Understand cycle implications

   Allowing revisits with strict increasing values can create cycles if not carefully handled, risking infinite loops.

2. Step 2: Identify safe approach

   DFS with memoization plus cycle detection prevents infinite recursion and correctly computes longest paths even with cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Memoization + cycle detection ensures correctness and termination [OK]

Hint: Cycle detection needed when revisits allowed [OK]

Common Mistakes:

• Using naive DFS causing infinite loops
• Ignoring cycles in topological sort
• Using BFS without value order