House Robber III

1-house-robber.js

export function rob(root) {
  const result = robRec(root);
  return Math.max(...result);
}

function robRec(node) {
  if (!node.left && !node.right) {
    return [node.data, 0];
  }
  const [includingRootLeft, excludingRootLeft] = node.left
    ? robRec(node.left)
    : [0, 0];
  const [includingRootRight, excludingRootRight] = node.right
    ? robRec(node.right)
    : [0, 0];
  // for each subtree, we calculate the max amount that can be robbed, in two variants
  // first is when we include the root node of the subtree
  // in this case we add the root node value with the values of the child trees where their root node is excluded
  // (since we cannot rob two directly connected nodes)
  // second is when we exclude the root node of the subtree
  // in this case we just take both including and excluding values of the child subtrees,
  // and find maximum
  return [
    // including root, should use excluding from child trees
    node.data + excludingRootLeft + excludingRootRight,
    // excluding root, should take whatever is max from child trees
    Math.max(includingRootLeft, excludingRootLeft) +
      Math.max(includingRootRight, excludingRootRight),
  ];
}

// time complexity
// we visit each node once, so O(n) where n is the number of nodes in binary tree
// depth of the call stack is O(n) since worst case height of binary tree is n (not balanced)

2-README.md

A thief has discovered a new neighborhood to target, where the houses can be represented as nodes in a binary tree, and 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.