Explore backtracking algorithm for solving complex problems like N-Queens, word search, binary tree paths, and Sudoku.

Coding

Systematically explores all possibilities to find solutions, often used in problems with multiple decision points, exploring, and undoing choices.

Backtracking

Efficiently prepare for coding interviews with strategies from FAANG engineers. Avoid the LeetCode grind and simplify your interview prep with real-world questions from top companies.

The ultimate guide to the System Design Interview – developed by Meta & Google engineers. Master distributed system fundamentals, and practice with real-world interview questions & mock interviews.

System Design

The essential guide to API Design & Product Design Interviews – developed by FAANG engineers. Master product design fundamentals & get hands-on with real-world APIs.

API Design

A battle-tested guide to Object Oriented Design Interviews – developed by FAANG engineers. Master OOD fundamentals & practice real-world interview questions.

Low Level Design Interview Using OOD Principles

Your essential EM Interview crash course. Learn strategies from FAANG hiring managers to demonstrate your leadership skills & experience to interviewers.

Engineering Management and Leadership Interviews

The ultimate guide to behavioral interviews. Developed by FAANG engineers. Use real-world questions, video recording, and structured strategies to get interview-ready in just a few hours.

Behavioral

# 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 approach 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 `include_root` and `exclude_root`.
   - `include_root` contains the maximum amount of money that can be robbed from the subtree rooted at the node with the `root` node included.
  - `exclude_root` 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 `include_root` and `exclude_root`, 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 `include_root`. 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 `exclude_root`.

- Finally, the `heist` function returns a pair containing the values of `include_root` and `exclude_root`.

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:




Let's solve the House Robber III problem using the Backtracking pattern.

Solution: House Robber III

Statement▼

Solution: House Robber III

Statement▼