Problem 337

Abstract / Summary

You must find the maximum amount of money that can be robbed from a tree of houses without robbing two directly connected houses.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0337.py

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        @cache
        def deeper(node, rob):
            if not node:
                return 0

            if rob:
                return deeper(node.left, False) + deeper(node.right, False) + node.val

            l = max(deeper(node.left,  True), deeper(node.left,  False))
            r = max(deeper(node.right, True), deeper(node.right, False))
            return l + r

        return max(deeper(root, True), deeper(root, False))
15 lines | 520 bytes | submitted August 30, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 56% (900k+ submissions).

Typical patterns to solve this problem:
  • Binary Tree
  • Depth First Search
  • Dynamic Programming
  • Tree
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation solves the classic “House Robber III” problem on a binary tree. The goal is to compute the maximum amount of money that can be collected without robbing two directly-connected nodes. The solution uses a depth-first recursion with memoization to explore both possibilities-robbing the current node or skipping it-while caching intermediate results to avoid repeated work.

Core Logic

The algorithm is centered around the nested function deeper. This helper receives a tree node and a Boolean flag rob that indicates whether the caller intends to rob the current node. The function returns the optimal amount that can be obtained from the subtree rooted at node under the given constraint.

@cache
def deeper(node, rob):
    if not node:
        return 0
    ...

The @cache decorator (from functools) automatically stores the result of each (node, rob) pair. Subsequent calls with the same arguments retrieve the cached value instantly, eliminating exponential recomputation.

When the Current Node Must Be Robbed

If rob is True, the algorithm is forced to include node.val in the total. Because two adjacent houses cannot both be robbed, the children must be visited with rob=False. The return expression adds the value of the current node to the optimal amounts from both subtrees when they are not robbed.

if rob:
    return deeper(node.left, False) + deeper(node.right, False) + node.val

When the Current Node May Be Skipped

When rob is False, the algorithm is free to decide for each child whether to rob it or not. It computes the best outcome for the left child by taking the maximum of robbing and not robbing that child, and does the same for the right child. The sum of these two maxima yields the optimal amount for the current subtree when the current node is not taken.

l = max(deeper(node.left,  True), deeper(node.left,  False))
r = max(deeper(node.right, True), deeper(node.right, False))
return l + r

Entry Point

The public method rob initiates the recursion by evaluating both possibilities for the root node-robbing it or not-and returns the larger of the two results.

return max(deeper(root, True), deeper(root, False))

Edge Cases Handled

The base case if not node: return 0 gracefully handles an empty tree, a missing child, or a completely null input. Because the function returns zero for a non-existent node, the recursion naturally collapses without special-case logic for leaf nodes. The same base case also covers trees consisting of a single node; the algorithm correctly returns either the node’s value (when robbed) or zero (when not robbed), and the outer max selects the appropriate amount.

When the tree is highly unbalanced-e.g., a chain of left children only-the memoization still prevents redundant calculations because each (node, rob) pair is cached exactly once, regardless of depth.

Performance Optimizations

The most significant optimization is the use of @cache. Without caching, the naïve recursion would explore an exponential number of state combinations, repeatedly evaluating identical subproblems. By storing the result of each (node, rob) pair, the algorithm reduces the effective work to a linear number of distinct states, proportional to the number of nodes times two (one for each Boolean flag).

Another subtle optimization is the early return for None nodes, which avoids unnecessary function calls deeper in the call stack. The decision to compute max only once per child (instead of recomputing the same sub-calls multiple times) further leverages the cache, ensuring that each child’s optimal values are retrieved from memory rather than recomputed.

The recursion follows a post-order traversal pattern: it first resolves the results for the left and right subtrees before combining them at the current node. This ordering aligns naturally with the cache’s ability to provide already-computed results for child subtrees, minimizing the call depth and keeping the call stack bounded by the height of the tree.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a row of houses shaped like a tree connected by branches. Each house has a pile of shiny gold coins inside. There is a sneaky rule for this game: if a house is chosen to be emptied, the houses directly touching it on either side must stay closed and quiet.

The code starts at the very top of the tree structure. It looks at a house and asks two questions. First, does it want to take the gold from this house? If the answer is yes, it adds those coins to its total but then must skip the houses immediately below it. Second, does it want to skip this house instead? if it skips, it is free to look at the houses below and pick the best pile from either the left or the right side.

To keep things fast, the code uses a special trick to remember the answer for every house it has already visited. This way, it never has to do the same work twice. It moves down the branches step by step, exploring every possible path, and keeps track of which choices lead to the biggest mountain of treasure. By the time it reaches the bottom of the tree, it has carefully weighed every option to find the secret path that lets it walk away with the most gold possible.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 8 | μ = 7.69 | σ = 1.03

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go TS
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github begeekmyfriend C
black-shadows C++
charles-wangkai Java
chenyanzhe C++
everthis JS
FelixFan1122 C#
fpdjsns C++
fsq C++
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
linouk23 C++
lkwq007 Python
MacJim C++
qiyuangong Python
ruoru Rust
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
vthwang Java
wisdompeak C++
XiaotaoGuo C++
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
begeekmyfriend C
black-shadows C++, C++
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
FelixFan1122 C#
fpdjsns C++
fsq C++
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
linouk23 C++
lkwq007 Python
MacJim C++
qiyuangong Python
ruoru Rust
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
vthwang Java
wisdompeak C++
XiaotaoGuo C++
zfang399 C++
46 links | 32 authors | 9 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

1 easy 2 medium 2 hard
6 solutions   August 30, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality