Day 8: House Robber III

Given the root of a binary tree where each node represents a house with money, return the maximum amount the thief can rob without robbing two directly connected houses. 

Before we get started let's take a deep breath…This is f%$! hard but it’s worth doing if you want to pursue a career in tech.

It took me some good time to wrap my head around this problem, so let’s take it step by step!

• What are we asked? Find the maximum amount of money a thief can rob from houses arranged in a binary tree, ensuring that no two directly linked houses are robbed on the same night.

• If you rob a house, its directly connected parent and child houses cannot be robbed, so you need to carefully choose which houses to rob to maximize the total amount stolen.

Refresher of House Robber I and House Robber II

Now before we continue, there is an important realization you’ll make when doing this problem. You can’t discriminate an entire level of nodes just because the test problems hint at that answer.

Here is how we visualize the problem:

There are 2 possibilities:

1. To Rob 
2. Not to Rob 

If we rob:

1. We Add the value to our sum 
2. We skip our children 

If we don’t rob:

1. We can decide to rob 
2. We can decide to skip 

And how will we know what to choose?

We calculate both! And get the max between both.

We will do that by allowing our function to return an array with the structure

{Rob, Not Rob}

We will leave everything to recursion to do its 🪄 

We calculate the left and right trees with both possibilities

 pair<int,int>left = helper(root->left); 
 pair<int,int>right = helper(root->right);

and now we compare!

 pair<int,int> helper(TreeNode* root ){
        if(root==NULL){
            return {0,0};
            //Rob , Not Rob
        }
        pair<int,int>left = helper(root->left); 
        pair<int,int>right = helper(root->right);
        int robThis = root->val + left.second + right.second; 
        int notRob  = max(left.first, left.second) + max(right.first, right.second); 
        return {robThis, notRob};
            
        }
        

    int rob(TreeNode* root) {
        if(root==NULL){
            return 0; 
        }
        pair<int,int> answer = helper(root); 
        return max(answer.first, answer.second);
         
    }
};

Let me invoke you into my cult

Media worth seeing

1. Mira Murati just created the first AI company run by adults apply here

2. Don’t blame me if you start seeing hearts everywhere, how to rewire your brain to find opportunities

3. How to turn your dark energy into charisma

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!