Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in JavaScript

House Robber III

Explore how to apply backtracking techniques to solve the House Robber III challenge, where you maximize theft from houses arranged as a binary tree while avoiding connected targets. This lesson helps you develop a strategy to evaluate each node and determine the highest amount of money that can be robbed without triggering alerts.

We'll cover the following...

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][1, 500].
  • 0≤0 \leq node.data ≤104\leq 10^4

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

House Robber III

1.

What is the maximum amount we can rob from the following array?

[3,4,5,2,3,null,1][3, 4, 5, 2, 3, null, 1]

A.

1717

B.

1111

C.

1010

D.

88

1 / 2

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

Try it yourself

Implement your solution in main.js in the following coding playground.

JavaScript
usercode > main.js
// Definition of a binary tree node

// class TreeNode {

//   constructor(data) {

//     this.data = data;

//     this.left = null;

//     this.right = null;

//   }

// }



import {TreeNode} from './ds_v1/BinaryTree.js';



function rob(root) {

    

    // Replace this placeholder return statement with your code

    return -1;

}



export {

    rob

}
House Robber III