Solution: House Robber III

Statement

A thief has discovered a new neighborhood to target, where the houses can be represented as nodes in a binary tree. 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 $[1, 500]$.
• $0 \leq$ node.data $\leq 10^4$

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 $2^n$ 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 the root node included.
• excludeRoot contains the maximum amount of money that can be robbed from the subtree rooted at the node with the root node excluded.

The function proceeds through the following steps:

• If the tree is empty, the heist function returns [0, 0], which represents the includeRoot and excludeRoot, 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 the includeRoot. It computes the maximum amount by adding the value of the root node to the following:

  • The maximum amount of money that can be robbed from the left subtree, excluding their respective parent node.
  • The 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 the root node itself, and store it in the excludeRoot.

• Finally, the Heist function returns a pair containing the values of includeRoot and excludeRoot.

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: