Solution: House Robber III
Let's solve the House Robber III problem using the Backtracking pattern.
Statement
A thief has discovered a new neighborhood to target, where the houses can be represented as nodes in a binary tree, and the money in the house is the data of the respective node. The thief can enter the neighborhood from a house represented as root
of the binary tree. Each house has only one parent house. The thief knows that if he robs two houses that are directly connected, the police will be notified. The thief wants to know the maximum amount of money he can steal from the houses without getting caught by the police. The thief needs your help determining the maximum amount of money he can rob without alerting the police.
Constraints:
- The number of nodes in the tree is in the range .
-
node.data
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
A naive approach to solving this problem involves calculating the sum of every possible valid combination of houses that can be robbed. A valid combination is one in which the thief does not rob two houses that are directly connected. After calculating all possible valid combinations, we can return the sum of the combination of houses that produces the maximum amount of money. This approach requires evaluating all possible ways to rob the neighborhood, which results in exponential time complexity. We can improve the algorithm’s efficiency by using backtracking.
Optimized solution using backtracking
An optimized approach to solve this problem is using backtracking, which involves recursively exploring all possible combinations and backtracking whenever we encounter an invalid combination. By doing so, we can avoid evaluating redundant solutions and reach the optimal combination more efficiently.
Our solution aims to find the maximum amount of money a thief can rob from the houses in a binary tree without alerting the police. The rob
function takes the root
node of the binary tree as input, calls the heist
function, and returns the maximum amount of money that the thief can rob from the binary tree.
The heist
function recursively calculates the maximum amount of money that can be robbed from a subtree rooted at a node. It returns a pair containing the values of includeRoot
and excludeRoot
.
includeRoot
contains the maximum amount of money that can be robbed from the subtree rooted at the node with theroot
node included.excludeRoot
contains the maximum amount of money that can be robbed from the subtree rooted at the node with theroot
node excluded.
The function proceeds through the following steps:
-
If the tree is empty, the heist function returns
[0, 0]
, which represents theincludeRoot
andexcludeRoot
, respectively. -
Otherwise, it recursively calculates the maximum amount of money that can be robbed from the left and right subtrees of the
root
node. -
Then, it stores the maximum amount of money that can be robbed from the
root
node in theincludeRoot
. It computes the maximum amount by adding the value of theroot
node to the following:- Maximum amount of money that can be robbed from the left subtree, excluding their respective parent node.
- Maximum amount of money that can be robbed from the right subtree, excluding their respective parent node.
-
Alternatively, it computes the sum of the maximum amount of money that can be robbed from both the left subtree and right subtree of the
root
node, excluding theroot
node itself, and store it in theexcludeRoot
. -
Finally, the
heist
function returns a pair containing the values ofincludeRoot
andexcludeRoot
.
The rob
function then returns the maximum value from the pair obtained by the heist
function, which is the maximum amount of money the thief can rob from the houses in a binary tree without alerting the police.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.