House Robber III

54.5k
0

A binary tree represents a group of houses. Every node contains a non-negative amount of money, and every edge directly connects a parent house with a child house.

Robbing both houses connected by one edge activates an alarm. Return the maximum amount of money obtainable from a valid selection of houses.

Example 1

Input: root = [3, 2, 3, null, 3, null, 1]
Output: 7
Explanation: Robbing the root and both leaf houses gives 3 + 3 + 1 = 7. No selected pair shares a parent-child edge.

Example 2

Input: root = [0]
Output: 0
Explanation: The only house contains no money, so the maximum obtainable amount equals 0.

Recursion

Each house presents a simple choice: rob it or skip it. If a house is robbed, both of its children must be skipped. If it is skipped, both children remain available to rob or skip. Applying the same choices recursively to every subtree explores all valid robbery plans.

The state solve(node, canRob) stores the maximum amount that can be robbed from the subtree rooted at node. When canRob is true, the current house can either be robbed or skipped. When canRob is false, the current house must be skipped because its parent was robbed. The initial call is solve(root, true) because the root has no parent restricting it.

Algorithm

  • Start with solve(root, true) because the root has no robbed parent and can be either robbed or skipped.

  • Return 0 for a null node because an empty subtree contributes nothing.

  • Calculate skipCurrent by solving both children with permission enabled, because skipping the current house leaves both children free to choose either option.

  • If canRob is false, return skipCurrent because a robbed parent forces the current house to be skipped.

  • Calculate robCurrent by solving both children with permission disabled, because robbing the current house prevents both children from being robbed.

  • Add the current house's value to the two blocked-child results.

  • Return max(skipCurrent, robCurrent) so the best valid choice for the current house is selected.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
// Creates one binary-tree node.
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
// Returns the best amount for one permission state.
int solve(TreeNode* node, bool canRob) {
// An empty subtree contributes no money.
if (node == nullptr) {
return 0;
}
// Skipping keeps both child houses available.
int skipLeft = solve(node->left, true);
int skipRight = solve(node->right, true);
int skipCurrent = skipLeft + skipRight;
// A robbed parent forces the current house to be skipped.
if (!canRob) {
return skipCurrent;
}
// Robbing blocks both direct child houses.
int robLeft = solve(node->left, false);
int robRight = solve(node->right, false);
int robCurrent = node->val + robLeft + robRight;
// The larger legal choice solves the current subtree.
return max(skipCurrent, robCurrent);
}
public:
// Returns the maximum valid robbery amount.
int rob(TreeNode* root) {
// No parent restriction exists above the root.
return solve(root, true);
}
};
// Driver code
int main() {
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(3);
root->right->right = new TreeNode(1);
Solution obj;
cout << obj.rob(root);
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the number of nodes, because each node can lead to at most two recursive choices, creating an exponential decision tree in the worst case.

Space Complexity: O(H), where H is the height of the tree, because the recursion stack stores at most one active call for each tree level.

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Memoization

Direct recursion can reach the same node with the same permission state multiple times. Since the subtree and permission flag completely determine the remaining problem, every such call produces the same answer. Memoization stores these answers so repeated states can be returned immediately.

A map named dp stores both permission states for every visited node. If a state is already cached, we return its stored answer; otherwise, we follow the same take-or-skip transitions as the recursive approach. This keeps the original recursive logic while eliminating repeated subtree calculations.

Algorithm

  • Start with an empty map named dp, because no node-state answer has been computed yet.

  • Use solve(node, canRob) with the same permission meaning as the recursive approach, so each cached value represents one exact subproblem.

  • Return 0 for a null node because an empty subtree contributes nothing and does not need to be stored.

  • When a node is first encountered, create two -1 entries for its permission states, using -1 as the uncalculated marker because valid robbery totals are non-negative.

  • If the current (node, canRob) state is already calculated, return its stored value immediately to avoid repeated recursion.

  • Calculate the skip value using the allowed states of both children, because skipping the current node leaves both children available to consider.

  • If robbing is allowed, calculate the rob value as the current node's value plus the blocked states of both children, because robbing the current node prevents both children from being robbed.

  • Store the resulting value in dp[node][state] so repeated visits to the same node and permission state can reuse it.

  • Return the allowed state of the root because the root has no parent restricting it.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
// Creates one binary-tree node.
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
unordered_map<TreeNode*, vector<int>> dp;
// Returns one cached permission-state answer.
int solve(TreeNode* node, bool canRob) {
// An empty subtree contributes no money.
if (node == nullptr) {
return 0;
}
// New nodes receive two uncalculated state markers.
if (dp.find(node) == dp.end()) {
dp[node] = vector<int>(2, -1);
}
int state = canRob ? 1 : 0;
// A stored state avoids repeated subtree work.
if (dp[node][state] != -1) {
return dp[node][state];
}
// Skipping keeps both child houses available.
int skipLeft = solve(node->left, true);
int skipRight = solve(node->right, true);
int skipCurrent = skipLeft + skipRight;
// A blocked state stores the forced skip result.
if (!canRob) {
dp[node][state] = skipCurrent;
return dp[node][state];
}
// Robbing blocks both direct child houses.
int robLeft = solve(node->left, false);
int robRight = solve(node->right, false);
int robCurrent = node->val + robLeft + robRight;
// The cache keeps the better legal choice.
dp[node][state] = max(skipCurrent, robCurrent);
return dp[node][state];
}
public:
// Returns the maximum valid robbery amount.
int rob(TreeNode* root) {
// A fresh call starts with no stored node states.
dp.clear();
return solve(root, true);
}
};
// Driver code
int main() {
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(3);
root->right->right = new TreeNode(1);
Solution obj;
cout << obj.rob(root);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of tree nodes, because two permission states are computed once for each node.

Space Complexity: O(N + H), where H is the tree height, because the dp map stores two values per node and the recursion stack stores at most H active calls. Since H ≤ N, this simplifies to O(N).

Tabulation

Memoization discovers states through recursive calls, while tabulation makes the dependency order explicit. Since each parent depends on the results of its children, we process the tree in postorder, ensuring both child states are available before calculating the parent.

An explicit stack replaces the recursion call stack. Each node is first marked as unprocessed and later as processed. When a processed node is reached, its two child states are already stored in dp, so we can calculate its blocked and allowed states using the same recurrence as the recursive approach.

Algorithm

  • Return 0 for an empty root because there are no states to process.

  • Push (root, false) onto an explicit stack, where false indicates the node has not been processed yet.

  • Pop an unprocessed node, push (node, true) back onto the stack, and then push its non-null children so they are processed before the parent.

  • When a processed node is popped, read the stored states of its children. Treat a missing child as [0, 0] because an empty subtree contributes nothing.

  • Add both children’s allowed values to calculate the blocked state, because a blocked node must be skipped.

  • Add the current node's value and both children’s blocked values to calculate the robbed state, because robbing the current node prevents both children from being robbed.

  • Store dp[node] = [blocked, max(blocked, robbed)] to preserve both states for the parent.

  • Return the root's allowed state because the root has no parent restricting it.Dry Run

House Robber III - Tabulation

House Robber III - Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
// Creates one binary-tree node.
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
public:
// Returns the maximum valid robbery amount.
int rob(TreeNode* root) {
// An empty tree has no robbery amount.
if (root == nullptr) {
return 0;
}
unordered_map<TreeNode*, vector<int>> dp;
stack<pair<TreeNode*, bool>> work;
work.push({root, false});
// Postorder guarantees completed child states.
while (!work.empty()) {
TreeNode* node = work.top().first;
bool processed = work.top().second;
work.pop();
// First visits schedule parent work after children.
if (!processed) {
work.push({node, true});
// The right child must finish before the parent.
if (node->right != nullptr) {
work.push({node->right, false});
}
// The left child must finish before the parent.
if (node->left != nullptr) {
work.push({node->left, false});
}
continue;
}
int leftBlocked = 0;
int leftAllowed = 0;
int rightBlocked = 0;
int rightAllowed = 0;
// A present left child supplies both states.
if (node->left != nullptr) {
leftBlocked = dp[node->left][0];
leftAllowed = dp[node->left][1];
}
// A present right child supplies both states.
if (node->right != nullptr) {
rightBlocked = dp[node->right][0];
rightAllowed = dp[node->right][1];
}
// A blocked node must use allowed child states.
int blocked = leftAllowed + rightAllowed;
// Robbing uses both blocked child states.
int robbed = node->val + leftBlocked + rightBlocked;
// Both permission states are stored together.
dp[node] = {blocked, max(blocked, robbed)};
}
// The root starts with robbery permission.
return dp[root][1];
}
};
// Driver code
int main() {
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(3);
root->right->right = new TreeNode(1);
Solution obj;
cout << obj.rob(root);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes, because each node is visited a constant number of times during the iterative postorder traversal.

Space Complexity: O(N), because the dp map and explicit postorder stack can each store up to N node entries.

Space Optimization

Tabulation stores a pair of values for every node, even though a parent only needs the results from its two children while processing that node. Instead, a postorder recursive call can return the pair directly. The parent combines the two child pairs, computes its own pair, and then the child results are no longer needed.

The returned pair keeps the same state meaning: index 0 stores the maximum amount when the current node is blocked by its parent, while index 1 stores the maximum amount when robbing the current node is allowed. Since no node-indexed dp table is maintained, only the pairs belonging to the active recursion path are stored.

Algorithm

  • Define solve(node) to return both permission states for the current subtree, so one postorder traversal provides everything the parent needs.

  • Return [0, 0] for a null node because an empty subtree contributes nothing in either state.

  • Recursively obtain the pairs from the left and right children before processing the current node, because its states depend on the completed child results.

  • Calculate blocked = left[1] + right[1], because when the current node is blocked, both children are free to be robbed or skipped.

  • Calculate robbed = node.val + left[0] + right[0], because robbing the current node blocks both children.

  • Calculate allowed = max(blocked, robbed), because when robbing the current node is allowed, we choose whichever option gives the larger amount.

  • Return [blocked, allowed] so the parent can use the appropriate state without storing a separate dp entry.

  • Return the allowed value from the root pair because the root has no parent restricting it.

Dry Run

House Robber III - Space Optimization

House Robber III - Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
// Creates one binary-tree node.
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
// Returns blocked and allowed subtree answers.
vector<int> solve(TreeNode* node) {
// An empty subtree contributes no money.
if (node == nullptr) {
return {0, 0};
}
// Child pairs are completed before the parent pair.
vector<int> left = solve(node->left);
vector<int> right = solve(node->right);
// Child states shift into the current pair.
// A blocked node must use allowed child states.
int blocked = left[1] + right[1];
// Robbing uses both blocked child states.
int robbed = node->val + left[0] + right[0];
// The allowed state keeps the larger legal choice.
int allowed = max(blocked, robbed);
// Returning the pair removes a node-indexed table.
return {blocked, allowed};
}
public:
// Returns the maximum valid robbery amount.
int rob(TreeNode* root) {
// The root starts with robbery permission.
return solve(root)[1];
}
};
// Driver code
int main() {
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(3);
root->right->right = new TreeNode(1);
Solution obj;
cout << obj.rob(root);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes, because the postorder traversal processes each node exactly once with constant work.

Space Complexity: O(H), where H is the height of the tree, because only recursion frames and returned values along one active root-to-leaf path are stored. In the worst case of a skewed tree, this becomes O(N).

Interview follow-up Questions

No. Only directly connected parent-child houses conflict, so a grandparent and a grandchild may both appear in a valid plan.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Print Longest Increasing Subsequence

Given an integer array arr , find one longest subsequence with values appearing in strictly increasing order. A subsequence keeps the original relative order but may skip any number of elements. Re...

115.1k
Dynamic Programming

Best Time to Buy and Sell Stock IV: At Most K Transactions

Given an integer k and an array prices , prices[day] stores the stock price on a particular day. At most k transactions may be completed. One transaction contains one buy followed by...

50.8k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Comments0