House Robber III solution and explanation
Google
9 more videos on this problem
House Robber III - Tree - Leetcode 337NeetCode · 18:02 · 63K views
House Robber 3 (LeetCode 337) | Full solution with diagrams | Dynamic Programming | Study AlgorithmsNikhil Lohia · 17:37 · 16K views
House Robber III | Live Coding with Explanation | Leetcode 337Algorithms Made Easy · 6:04 · 4K views
House Robber III | Leet code 337 | Theory explained + Python codeSai Anish Malla · 15:31 · 940 views
LeetCode 337 House Robber III | Dynamic Programming | Recursion with Memorization | TreeCode Harmony · 14:22 · 790 views
House Robber III | Binary Tree | Recursion + Memoization | LeetCode 337 | C++ | PythonClashing Coder · 18:46 · 689 views
LeetCode 337. House Robber IIIHappy Coding · 14:30 · 455 views
House Robber III | Letcodee 337 | Live coding session 🔥🔥🔥Coding Decoded · 1:36 · 405 views
Daily Leetcode #237: Nov 23, 2020 - 337. House Robber IIIProgramming Live with Larry · 14:51 · 248 views
337. House Robber III | LeetCode Medium | Python Solution | Tree, DFS, Dynamic ProgrammingShaheer Keerirakath · 3:08 · 128 views
The problem
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:
Input: root = [3,2,3,null,3,null,1] Output: 7 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: root = [3,4,5,1,3,null,1] Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. 0 <= Node.val <= 104
Approach overview
Problem Overview: Each node in a binary tree represents a house containing money. If you rob a house, you cannot rob its direct children. The goal is to compute the maximum amount of money you can steal without triggering the alarm.
This is a tree variant of the classic House Robber problem. Instead of a linear array, houses form a binary tree. The restriction applies between a node and its children, which naturally leads to a recursive decision at every node: rob it or skip it.
Approach 1: Brute Force DFS (Exponential Time)
Traverse the tree using Depth-First Search. For each node, compute two choices: rob the current node (which means skipping its children and exploring grandchildren) or skip the node (which allows exploring both children). The algorithm recursively evaluates both scenarios and returns the larger value. This approach repeatedly recomputes the same subtrees, causing exponential growth in work. Time complexity is O(2^n) in the worst case, and recursion depth requires O(h) space where h is the tree height.
Approach 2: Recursive DFS with Memoization (O(n))
The key observation: the maximum loot for a subtree rooted at a node is always the same regardless of how many times it is reached. Store the computed result for each node in a hash map (memo table). When DFS visits a node again, return the cached value instead of recomputing it.
For each node, compute:
rob = node.val + value(grandchildren)
skip = value(left child) + value(right child)
The result for that node is max(rob, skip). Memoization ensures each node's value is calculated once. This transforms the algorithm into a classic Dynamic Programming on trees problem. The DFS visits every node once, giving O(n) time complexity. The memo table stores results for up to n nodes, so space complexity is O(n) with recursion stack up to O(h).
This pattern is often called tree DP: compute optimal values for subtrees and reuse them while exploring the tree. Memoization prevents recomputation of overlapping subproblems, which is the main bottleneck in the brute force solution.
Recommended for interviews: The DFS with memoization approach is the expected solution. Interviewers want to see that you first recognize the rob/skip decision pattern from House Robber I, then adapt it to a tree structure using recursion. Explaining the brute force approach briefly shows understanding of the decision space, while introducing memoization demonstrates strong dynamic programming intuition.
Approach 1: Recursive Approach with Memoization
This approach uses recursion along with memoization to store the maximum robbery amount for each node of the tree. The idea is to leverage a helper function that returns two values for each node: maximum money if the current node is included and maximum money if the current node is not included. At each node, we have two choices: either rob this node or not rob it, and for each choice, there are further choices for child nodes and so on.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def rob(self, root: TreeNode) -> int:
def helper(node):
if not node:
return (0, 0) # (max if not robbed, max if robbed)
left = helper(node.left)
right = helper(node.right)
rob = node.val + left[0] + right[0]
not_rob = max(left) + max(right)
return (not_rob, rob)
return max(helper(root))class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public int rob(TreeNode root) {
int[] result = robSub(root);
return Math.max(result[0], result[1]);
}
private int[] robSub(TreeNode node) {
if (node == null) return new int[2];
int[] left = robSub(node.left);
int[] right = robSub(node.right);
int rob = node.val + left[0] + right[0];
int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[] {notRob, rob};
}
}#include <unordered_map>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
unordered_map<TreeNode*, int> robMemo, notRobMemo;
public:
int rob(TreeNode* root) {
return max(robHouse(root, true), robHouse(root, false));
}
private:
int robHouse(TreeNode* node, bool canRob) {
if (!node) return 0;
if (canRob) {
if (robMemo.find(node) != robMemo.end()) return robMemo[node];
int rob = node->val + robHouse(node->left, false) + robHouse(node->right, false);
int notRob = robHouse(node->left, true) + robHouse(node->right, true);
robMemo[node] = max(rob, notRob);
return robMemo[node];
} else {
if (notRobMemo.find(node) != notRobMemo.end()) return notRobMemo[node];
int result = robHouse(node->left, true) + robHouse(node->right, true);
notRobMemo[node] = result;
return result;
}
}
};function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var rob = function(root) {
const helper = (node) => {
if (!node) return [0, 0];
const left = helper(node.left);
const right = helper(node.right);
const rob = node.val + left[0] + right[0];
const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return [notRob, rob];
};
const result = helper(root);
return Math.max(result[0], result[1]);
};#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct Robbery {
int withRob;
int withoutRob;
};
struct Robbery helper(struct TreeNode* node) {
if (!node) {
struct Robbery empty = {0, 0};
return empty;
}
struct Robbery left = helper(node->left);
struct Robbery right = helper(node->right);
struct Robbery current;
current.withRob = node->val + left.withoutRob + right.withoutRob;
current.withoutRob = (left.withRob > left.withoutRob ? left.withRob : left.withoutRob) +
(right.withRob > right.withoutRob ? right.withRob : right.withoutRob);
return current;
}
int rob(struct TreeNode* root) {
struct Robbery result = helper(root);
return result.withRob > result.withoutRob ? result.withRob : result.withoutRob;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public int Rob(TreeNode root) {
var res = RobSub(root);
return Math.Max(res[0], res[1]);
}
private int[] RobSub(TreeNode node) {
if (node == null) return new int[2];
int[] left = RobSub(node.left);
int[] right = RobSub(node.right);
int rob = node.val + left[0] + right[0];
int notRob = Math.Max(left[0], left[1]) + Math.Max(right[0], right[1]);
return new int[] { notRob, rob };
}
}The helper function returns two values for each node. It uses recursion to visit each node in the tree, calculating the maximum robbery amount when the current node is included or not. For each node, if it's robbed, the children cannot be robbed; else, we take the maximum of robbing or not robbing the children. The final result is the maximum of the helper(root) values.
Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited only once. Space Complexity: O(N) due to the recursion stack space in the worst case of a skewed tree.
Approach 2: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function rob(root: TreeNode | null): number {
const dfs = (root: TreeNode | null): [number, number] => {
if (!root) {
return [0, 0];
}
const [la, lb] = dfs(root.left);
const [ra, rb] = dfs(root.right);
return [root.val + lb + rb, Math.max(la, lb) + Math.max(ra, rb)];
};
return Math.max(...dfs(root));
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
var dfs func(*TreeNode) (int, int)
dfs = func(root *TreeNode) (int, int) {
if root == nil {
return 0, 0
}
la, lb := dfs(root.Left)
ra, rb := dfs(root.Right)
return root.Val + lb + rb, max(la, lb) + max(ra, rb)
}
a, b := dfs(root)
return max(a, b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited only once. Space Complexity: O(N) due to the recursion stack space in the worst case of a skewed tree. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS | O(2^n) | O(h) | Conceptual starting point to understand rob vs skip decisions |
| DFS with Memoization (Tree DP) | O(n) | O(n) | Optimal solution for interviews and production code |
Frequently asked questions
Is House Robber III easy or hard?
House Robber III is rated Medium on LeetCode but can feel closer to hard for beginners because it combines dynamic programming with tree traversal. Once you recognize the rob-or-skip decision pattern and apply memoization, the implementation becomes straightforward.
House Robber III Python/Java solution
Python and Java solutions typically implement recursive DFS with a memoization map. Each function call evaluates rob and skip cases for the node and caches the result. This ensures O(n) time complexity and works efficiently even for large trees.
How to solve House Robber III in O(n)?
Traverse the tree using DFS and store the computed maximum profit for each node in a memo table. For each node calculate two cases: rob the node and add values from grandchildren, or skip the node and add values from its children. Memoization ensures every subtree result is computed only once, giving O(n) time.
What is the best approach for House Robber III?
The best approach uses Depth-First Search with memoization. For every node you compute the maximum profit from robbing it or skipping it, then store the result in a hash map to avoid recomputation. This converts the problem into dynamic programming on a tree and runs in O(n) time.
Is House Robber III asked at Google/Amazon/Meta?
House Robber III represents a classic tree dynamic programming pattern and has appeared in interviews at companies like Amazon, Google, and Meta. Interviewers use it to test recursion, DFS traversal, and the ability to apply memoization on tree structures.
What data structure is used in House Robber III?
The problem primarily uses a binary tree with Depth-First Search traversal. A hash map (dictionary) is typically used for memoization to store computed results for each node, enabling dynamic programming over the tree structure.
What is the time complexity of House Robber III?
The optimal memoized DFS solution runs in O(n) time because each node in the binary tree is processed once. Space complexity is O(n) for the memoization map plus O(h) recursion stack where h is the tree height.