House Robber III - Practice Coding Problems

House Robber III - Problem

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root. Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree.

It will automatically contact the police if two directly-linked houses were broken into on the same night. Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Input & Output

Example 1 — Basic Tree

$ Input: root = [3,2,3,null,3,null,1]

› Output: 7

💡 Note: Rob nodes 3, 3, and 1 for maximum sum. Cannot rob adjacent nodes (parent-child), so skip the middle level nodes with value 2 and 3.

Example 2 — Simple Tree

$ Input: root = [3,4,5,1,3,null,1]

› Output: 9

💡 Note: Rob nodes 4, 3, and 1 for sum = 4 + 3 + 1 = 8. Or rob nodes 3 and 5 for sum = 3 + 5 = 8. Or rob root 3 and leaves 1,3,1 for sum = 3 + 1 + 3 + 1 = 8. Actually, rob 4 + 5 = 9 is optimal.

Example 3 — Single Node

$ Input: root = [5]

› Output: 5

💡 Note: Only one house to rob, so rob it for value 5.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
0 ≤ Node.val ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree where each node represents a house with money value

Constraint

Cannot rob two directly connected houses (parent-child relationship)

Find Maximum

Return maximum money that can be robbed following the constraint

Key Takeaway

🎯 Key Insight: For each node, choose to rob it (skip children) or skip it (consider children) - track both states optimally

Asked in

a Amazon 15 f Facebook 12 G Google 8 M Microsoft 6

The key insight is that for each node we have two choices: rob it (and skip children) or skip it (and potentially rob children). The optimal solution uses DFS with state tracking, maintaining [rob, skip] values for each subtree. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(2ⁿ)	O(h)	Try all combinations by recursively choosing to rob or skip each node
Optimal DFS (Bottom-Up State Tracking)	O(n)	O(h)	Single DFS pass tracking both rob and skip states for each node
Memoization (Top-Down DP)	O(n)	O(n)	Cache results of subproblems to avoid recalculation

Brute Force Recursion — Algorithm Steps

Step 1: For current node, calculate max if we rob it (node value + rob grandchildren)
Step 2: Calculate max if we skip it (rob left child + rob right child)
Step 3: Return maximum of both scenarios

Visualization

Tap to expand

Step-by-Step Walkthrough

Rob Node

Calculate value if we rob current node + grandchildren

Skip Node

Calculate value if we skip current node + rob children

Take Maximum

Return the better of the two choices

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    // Rob current node - skip children, rob grandchildren
    int robCurrent = root->val;
    if (root->left) {
        robCurrent += solution(root->left->left) + solution(root->left->right);
    }
    if (root->right) {
        robCurrent += solution(root->right->left) + solution(root->right->right);
    }
    
    // Skip current node - can rob children
    int skipCurrent = solution(root->left) + solution(root->right);
    
    return robCurrent > skipCurrent ? robCurrent : skipCurrent;
}

int main() {
    // Simple test case: [3,2,3,null,3,null,1]
    struct TreeNode* root = createNode(3);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->right = createNode(3);
    root->right->right = createNode(1);
    
    printf("%d\n", solution(root));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each node branches into 2 recursive calls, creating exponential growth

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

185.0K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler