Bird
Raised Fist0
Interview Prepdp-advanced-trees-bitmaskmediumAmazonGoogle

House Robber III (On Tree)

Choose your preparation mode4 modes available
</>
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
}
0/10
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
t1_01basic
Input{"root":[3,2,3,null,3,null,1]}
Expected7

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

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

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

t2_01edge
Input{"root":null}
Expected0

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

t2_02edge
Input{"root":[10]}
Expected10

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

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

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

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

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

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

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

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

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

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

Test to catch confusion between 0/1 and unbounded knapsack logic on tree 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}
⏱ Performance - must finish in 2000ms

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

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

  1. Step 1: Understand traversal order requirement

    The problem requires visiting root before left and right subtrees, which is preorder traversal.
  2. 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.
  3. Final Answer:

    Option C -> Option C
  4. 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. Consider the following code snippet implementing the optimal countNodes function for a complete binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final return value of countNodes(root)?
easy
A. 4
B. 3
C. 5
D. 6

Solution

  1. Step 1: Calculate tree height

    Height h = 3 (nodes 1 -> 2 -> 4).
  2. Step 2: Binary search on last level nodes

    Last level has indices 0 to 3. Check existence: - idx=0 exists (node 4) - idx=1 does not exist So left ends at 1.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Count = (2^(3-1)-1) + left = 3 + 1 = 4 [OK]
Hint: Count = perfect nodes + last level nodes found [OK]
Common Mistakes:
  • Off-by-one in binary search bounds
  • Miscounting last level nodes
3. Given a binary tree, you need to find the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. Which approach guarantees an optimal solution to this problem?
easy
A. Perform a postorder traversal computing heights and update the diameter at each node using recursion with a global variable.
B. Apply dynamic programming with memoization on node pairs to find longest paths.
C. Use a greedy traversal that always chooses the deeper subtree at each node.
D. Calculate the height of the tree and multiply by two to estimate the diameter.

Solution

  1. Step 1: Understand the problem requires the longest path between any two nodes, not necessarily passing through root.

    The diameter can be found by checking the sum of left and right subtree heights at every node.
  2. Step 2: Recognize that a postorder traversal with recursion and a global variable to track diameter updates at each node ensures all paths are considered.

    This approach visits each node once, updating the diameter with left_height + right_height.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Postorder traversal with global diameter update covers all nodes [OK]
Hint: Diameter updates at every node, not just root [OK]
Common Mistakes:
  • Thinking diameter must pass through root
  • Using greedy to pick deeper subtree only
  • Confusing diameter with twice height
4. You are given a binary tree and a target sum. You need to determine if there exists a root-to-leaf path such that adding up all the values along the path equals the target sum. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Depth-first search (DFS) with early stopping upon finding a valid path
B. Greedy traversal choosing the child with the closest value to the target sum
C. Dynamic programming with memoization of partial sums at each node
D. Breadth-first search (BFS) exploring all paths level by level

Solution

  1. Step 1: Understand the problem constraints

    The problem requires checking if any root-to-leaf path sums to the target. This naturally fits a tree traversal pattern.
  2. Step 2: Identify the best approach

    DFS with early stopping is optimal because it explores paths deeply and stops as soon as a valid path is found, avoiding unnecessary work.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    DFS explores paths fully and stops early when possible [OK]
Hint: Early stopping DFS avoids unnecessary traversal [OK]
Common Mistakes:
  • Believing greedy approach works for sums
  • Confusing BFS with DFS for path sums
5. Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? Tree structure: - root = TreeNode(5) - root.left = TreeNode(4) - root.right = TreeNode(8) - root.left.left = TreeNode(11) - root.left.left.left = TreeNode(7) - root.left.left.right = TreeNode(2) - root.right.left = TreeNode(13) - root.right.right = TreeNode(4) - root.right.right.right = TreeNode(1)
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if not node.left and not node.right:
            return curr_sum == targetSum
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)
easy
A. True
B. False
C. Raises an exception due to null pointer
D. Returns True only if the root value equals targetSum

Solution

  1. Step 1: Trace the path sums

    Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.
  2. Step 2: Confirm code logic

    The DFS returns True as soon as it finds the matching path sum at a leaf node.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Path 5↔4↔11↔2 sums to 22, so return True [OK]
Hint: Check all root-to-leaf paths, not just partial sums [OK]
Common Mistakes:
  • Stopping at non-leaf nodes
  • Ignoring leaf node condition
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard