Log inSign up
mediumleetcodeNot Started

House Robber III

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1 · Example 1: Rob Root and Grandchildren:

Input: root = [3, 2, 3, null, 3, null, 1] Tree: 3 / \ 2 3 \ \ 3 1
Output: 7
Explanation: Maximum amount = 3 (root) + 3 (grandchild) + 1 (grandchild) = 7.

Example 2 · Example 2: Rob Children Instead of Root:

Input: root = [3, 4, 5, 1, 3, null, 1] Tree: 3 / \ 4 5 / \ \ 1 3 1
Output: 9
Explanation: Maximum amount = 4 + 5 = 9.

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • 0 <= Node.val <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master state DP on trees returning multiple values from subtrees.
  • Understand the include/exclude dependency between parent and children.
  • Achieve single-pass O(n) runtime with zero memoization hash map allocations.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Maximum weight independent set on a tree.
  • Cannot pick directly connected / adjacent tree nodes.
  • Include / Exclude DP on trees.

Algorithmic Decision Tree:

  • Base case: if node == null -> return [0, 0].
  • rob = node.val + left.notRob + right.notRob.
  • notRob = max(left.rob, left.notRob) + max(right.rob, right.notRob).

Connected Patterns:

House RobberHouse Robber IIBinary Tree Maximum Path Sum

1. Exponential Recursion (Root vs Grandchildren)

Intuition

If we rob root, sum root.val + rob(root.left.grandchildren) + rob(root.right.grandchildren). If we don't, sum rob(root.left) + rob(root.right). Take max.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If root == null return 0.
  2. Step 2: valRob = root.val + recurse on grandchildren.
  3. Step 3: valSkip = recurse on root.left + recurse on root.right.
  4. Step 4: Return max(valRob, valSkip).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int rob(TreeNode* root) {
10 if (!root) return 0;
11 int robRoot = root->val;
12 if (root->left) {
13 robRoot += rob(root->left->left) + rob(root->left->right);
14 }
15 if (root->right) {
16 robRoot += rob(root->right->left) + rob(root->right->right);
17 }
18 int skipRoot = rob(root->left) + rob(root->right);
19 return max(robRoot, skipRoot);
20 }
21};
22
23int main() {
24 // Sample driver execution
25 cout << "Execution completed successfully." << endl;
26 return 0;
27}
28

Time & Space Complexity

  • Time complexity: O(2^n) — Overlapping subproblems cause exponential branching.
  • Space complexity: O(h) — Call stack bounded by tree height h.

2. Top-Down DP with Hash Map Memoization

Intuition

Store memo[node] = max money rob-able from subtree rooted at node. If node in memo, return memo[node] immediately.

When to apply: Top-down memoization approach.

Algorithm

  1. Step 1: If root in memo, return memo[root].
  2. Step 2: robRoot = root.val + sum(grandchildren).
  3. Step 3: skipRoot = rob(root.left) + rob(root.right).
  4. Step 4: memo[root] = max(robRoot, skipRoot). Return memo[root].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 unordered_map<TreeNode*, int> memo;
9public:
10 int rob(TreeNode* root) {
11 if (!root) return 0;
12 if (memo.count(root)) return memo[root];
13 int robRoot = root->val;
14 if (root->left) robRoot += rob(root->left->left) + rob(root->left->right);
15 if (root->right) robRoot += rob(root->right->left) + rob(root->right->right);
16 int skipRoot = rob(root->left) + rob(root->right);
17 return memo[root] = max(robRoot, skipRoot);
18 }
19};
20
21int main() {
22 // Sample driver execution
23 cout << "Execution completed successfully." << endl;
24 return 0;
25}
26

Time & Space Complexity

  • Time complexity: O(n) — Each node evaluated once; grandchildren lookups hit memo.
  • Space complexity: O(n) — Hash map stores all n nodes.

3. Bottom-Up Tree DP Returning [rob, notRob] Pair

Intuition

Every node returns [rob, notRob]. rob = node.val + left.notRob + right.notRob. notRob = max(left.rob, left.notRob) + max(right.rob, right.notRob). No memoization map needed.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: Helper dfs(node): if null return [0, 0].
  2. Step 2: left = dfs(node.left); right = dfs(node.right).
  3. Step 3: robThis = node.val + left[1] + right[1].
  4. Step 4: notRobThis = max(left[0], left[1]) + max(right[0], right[1]).
  5. Step 5: Return [robThis, notRobThis]. Overall answer = max(result[0], result[1]).

Tree DP Trace for root = [3, 2, 3]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Leaves 2 and 3
Visual state
Values and pointers at this exact step
tree
Root
3
L
2 [rob:2, not:0]
R
3 [rob:3, not:0]

Node order shown; add connections to display explicit tree edges.

subtrees: 2
Check / comparison
Leaves evaluated independently.
Decision / next transition
Pass states up to root 3.
Why this step matters

Step 1: Leaves 2 and 3. For leaf 2: [rob: 2, notRob: 0]. For leaf 3: [rob: 3, notRob: 0].

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 pair<int, int> dfs(TreeNode* node) {
9 if (!node) return {0, 0};
10 auto [lRob, lNot] = dfs(node->left);
11 auto [rRob, rNot] = dfs(node->right);
12 int robThis = node->val + lNot + rNot;
13 int notRobThis = max(lRob, lNot) + max(rRob, rNot);
14 return {robThis, notRobThis};
15 }
16public:
17 int rob(TreeNode* root) {
18 auto [r, nr] = dfs(root);
19 return max(r, nr);
20 }
21};
22
23int main() {
24 // Sample driver execution
25 cout << "Execution completed successfully." << endl;
26 return 0;
27}
28

Time & Space Complexity

  • Time complexity: O(n) — Single postorder traversal; each node computed once in O(1).
  • Space complexity: O(h) — Call stack bounded by tree height h.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Exponential RecursionO(2^n)O(h)Separate root+grandchildren vs children calls.Repeated subtree recomputation.
2.Top-Down MemoizationO(n)O(n)Memoize subtree answers in hash map.Hash map operations.
3.Bottom-Up [rob, notRob] DPOptimalO(n)O(h)Single postorder traversal returning 2-element state pair.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node: return root.val.
  • All zero values: return 0.
  • Linear / Skewed tree: reduces to standard 1D House Robber problem.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast brute force with memoization (O(n) time, O(n) hash map space) with the pair return DP (O(n) time, O(h) recursion space).
  2. Emphasize why notRob takes max(rob, notRob) for each child: skipping a parent doesn't FORCE children to be robbed; it merely PERMITS them to be robbed if profitable.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When current node is NOT robbed, why is notRobThis computed as max(lRob, lNot) + max(rRob, rNot) rather than simply lRob + rRob?

Back to DSA Sheet