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 Python code implementing the Morris Preorder Traversal approach to sum root-to-leaf numbers. Given the binary tree: 1 / \ 2 3 What is the final value of the variable total returned by sumNumbers?

easy

A. 5

B. 15

C. 25

D. 26

Solution

1. Step 1: Trace path 1->2

   current_number accumulates 1 then 12; leaf node 2 adds 12 to total.

2. Step 2: Trace path 1->3

   current_number resets to 1, then accumulates 13; leaf node 3 adds 13 to total. Total = 12 + 13 = 25.

3. Step 3: Check for off-by-one or missed increments

   Integer division after visiting left subtree correctly adjusts current_number; no extra addition occurs.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Sum of 12 and 13 is 25, matching code behavior [OK]

Hint: Trace current_number updates carefully at each node [OK]

Common Mistakes:

• Off-by-one in current_number division
• Adding non-leaf nodes to total

2. You are given a binary tree and need to determine if it is a mirror of itself (i.e., symmetric around its center). Which approach guarantees an optimal solution that efficiently checks this property by comparing nodes in a mirrored fashion?

easy

A. Use a recursive DFS that simultaneously compares the left subtree of one node with the right subtree of the other node, returning false immediately on mismatch.

B. Perform a level-order traversal and compare nodes at each level from left to right.

C. Traverse the tree in preorder and check if the sequence of node values is a palindrome.

D. Use a brute force approach that generates all subtree permutations and checks for symmetry.

Solution

1. Step 1: Understand the problem requires mirrored subtree comparison

   The problem asks if the tree is symmetric, meaning the left subtree is a mirror reflection of the right subtree.

2. Step 2: Identify the approach that compares mirrored nodes recursively with early exit

   The recursive DFS approach compares left subtree nodes with right subtree nodes in mirrored positions and returns false immediately if any mismatch is found, ensuring efficiency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mirrored recursive DFS matches problem requirements [OK]

Hint: Symmetry requires mirrored subtree comparison [OK]

Common Mistakes:

• Assuming preorder traversal palindrome check works
• Using level-order traversal without mirrored comparison
• Trying brute force subtree permutations

3. What is the time complexity of the optimized recursive solution that uses a hash map for index lookup when constructing a binary tree from inorder and postorder traversals of size n?

medium

A. O(n) because each node is processed once and index lookup is O(1)

B. O(n^2) due to repeated slicing of arrays

C. O(n log n) because of balanced tree recursion depth

D. O(n) but with O(n) auxiliary space for recursion stack and hash map

Solution

1. Step 1: Analyze time complexity

   Using a hash map avoids repeated linear searches, so each node is processed once -> O(n) time.

2. Step 2: Analyze space complexity

   Hash map stores n elements, recursion stack can be up to O(n) in skewed trees, so total auxiliary space is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time is O(n), space includes recursion stack and hash map [OK]

Hint: Hash map reduces search to O(1), recursion stack adds O(n) space [OK]

Common Mistakes:

• Assuming slicing causes O(n^2) time
• Ignoring recursion stack space
• Confusing balanced tree depth with complexity

4. Consider the following buggy code snippet for building a binary tree from preorder and inorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or infinite loops?

medium

A. Line where stack is initialized with root

B. Line inside if block missing stack.append(node.left)

C. Line where root is initialized with preorder[0]

D. Line inside else block where inorder_index is incremented

Solution

1. Step 1: Identify missing operation

   Inside the if block, after creating node.left, the new node is not pushed onto the stack.

2. Step 2: Consequences of missing stack append

   Without pushing, the algorithm loses track of the left subtree root, causing incorrect tree or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Stack must track all nodes to correctly build tree [OK]

Hint: Always push newly created nodes to stack to track subtree roots [OK]

Common Mistakes:

• Forgetting to push left child nodes
• Incorrectly incrementing inorder_index
• Misinitializing root or stack

5. What is the time complexity of the optimal DFS with early stopping solution for the Path Sum problem on a binary tree with n nodes and height h?

medium

A. O(h) because the recursion only goes down one path at a time

B. O(n^2) because each node's sum is recalculated multiple times

C. O(n) because in the worst case all nodes are visited once

D. O(log n) assuming the tree is balanced

Solution

1. Step 1: Identify worst-case traversal

   In the worst case, the algorithm visits every node once to check all root-to-leaf paths.

2. Step 2: Analyze recursion and early stopping

   Early stopping can prune some paths, but worst case still requires full traversal, so time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Each node visited once -> O(n) time [OK]

Hint: Worst case requires visiting all nodes once [OK]

Common Mistakes:

• Confusing height with total nodes
• Assuming early stopping always reduces complexity