House Robber III

Problem Statement

LeetCode-337: The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the 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.

Approach

This is an extension of the House Robber problem with a slight twist. The houses are now represented as nodes in a binary tree. The thief can’t rob two adjacent houses. In this case, the adjacent houses are the nodes that are directly connected via a direct edge.

The problem can be solved using a recursive approach. The idea is to traverse the tree in a bottom-up manner. At each node, we have two choices:

1. Rob the current node and skip the children.
2. Skip the current node and rob the children. For the children, we again have these two choices i.e. rob the children or skip them and proceed to grandchildren.

The maximum amount of money that can be robbed at each node is the maximum of the two choices. The base case of the recursion is when the node is null. In this case, the maximum amount of money that can be robbed is 0.

Implementation

Here is a Java implementation of the approach:

// a private record to store the maximum amount of money that can be robbed
// with and without the current node
private record Loot(int withNode, int withoutNode){
}

public int rob(TreeNode root) {
    Loot loot = letsRob(root);
    return Math.max(loot.withNode, loot.withoutNode);
}

private Loot letsRob(TreeNode root){
    if(null == root){
        return new Loot(0,0);
    }
    Loot left = letsRob(root.left);
    Loot right = letsRob(root.right);

    // the maximum amount of money that can be robbed with 
    // and without the current node
    int withRoot = root.val + left.withoutNode + right.withoutNode;
    int withoutRoot = Math.max(left.withNode, left.withoutNode) 
                        + Math.max(right.withNode, right.withoutNode);

    return new Loot(withRoot, withoutRoot);                                    
}

Complexity Analysis

As the approach requires us to visit all the nodes once, the time complexity for this approach is $O(n)$ where $n$ is the number of nodes in the binary tree.