House Robber III

A thief can rob houses but cannot rob adjutant houses return maximum money he can steal

House Robber III

Problem Statement

A thief has found a new place to rob. There is only one entrance to this area, called root.

Besides the root, every house has exactly one parent house. After scouting the area, the thief realizes that all the houses form a binary tree. If two directly-linked houses (a parent and its child) are both robbed on the same night, the police will automatically be alerted.

Given the root of this binary tree, return the maximum amount of money the thief can rob without alerting the police.

Solution

We solve this using recursion, working from the leaves of the tree back up to the root.

The Idea

For every house (node) in the tree, there are always two choices:

• Include this house in the robbery.
• Exclude this house from the robbery.

At each node, we calculate the best possible amount for both choices, and pass this information back up to the parent node.

Steps

• We use a helper function, heist(root), which returns an array of two values: [amountIfIncluded, amountIfExcluded].
• If the current node is empty (null), there's nothing to rob here, so we return [0, 0].
• Otherwise, we first get the results for the left subtree and the right subtree, by calling heist recursively.
• We then calculate our two choices for the current node:
  • If we include this node: We add the current node's value to the amount we'd get by excluding both of its children (since we can't rob a house and its direct child on the same night).
  • If we exclude this node: We take the best possible amount from each child — whichever is larger between including or excluding that child — and add those together. Since we're not robbing this node, there's no restriction on whether its children are robbed or not.
• We return both of these values, [included, excluded], back up to the parent.
• Once we reach the very top of the tree (the root), we simply take the larger of the two final values — whether the root itself was included or excluded — as our answer.

Code

var rob = function(root) {

    function heist(root) {

        if (!root) {
            return [0, 0];
        }

        let leftSubTree = heist(root.left);
        let rightSubTree = heist(root.right);

        let rootIncluded = root.val + leftSubTree[1] + rightSubTree[1];
        let rootExcluded = Math.max(leftSubTree[0], leftSubTree[1]) + Math.max(rightSubTree[0], rightSubTree[1]);

        return [rootIncluded, rootExcluded];
    }

    const result = heist(root);

    return Math.max(result[0], result[1]);

};