Skip to main content
Talentd

House Robber III - Solution & Explanation

MediumDynamic ProgrammingTreeDepth-First SearchBinary Tree12 min readAsked at: Amazon, Microsoft, Meta +10
Practice this problem

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:

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.

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.

Code

PythonC++JavaScriptC#JavaC

Python

C++

JavaScript

C#

Java

C

Complexity

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.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force DFSO(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

Video Solution

House Robber III - Tree - Leetcode 337 • NeetCode • 63,170 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice House Robber III with our built-in code editor and test cases.

Practice on FleetCode
Previous

House Robber

Next

House Robber II