
### Problem Statement

###### 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.

![House Robber](https://assets.leetcode.com/uploads/2021/03/10/rob2-tree.jpg)

**INPUT**

- root = [3,4,5,1,3,null,1]

**OUTPUT**

- 9

**EXPLANATION**

- Maximum amount of money the thief can rob = 4 + 5 = 9.

**Steps To Solve**

- Think of solution without code

  - At first glance, the problem exhibits the feature of "optimal substructure": if we want to rob maximum amount of money from current binary tree (rooted at root), we surely hope that we can do the same to its left and right subtrees.
  - So going along this line, let's define the function rob(root) which will return the maximum amount of money that we can rob for the binary tree rooted at root; the key now is to construct the solution to the original problem from solutions to its subproblems, i.e., how to get rob(root) from rob(root.left), rob(root.right), ... etc.
  - Let us consider include exclude approach.

    ![House Robber](https://assets.leetcode.com/uploads/2021/03/10/rob2-tree.jpg)

  - Lets take top three node here 3,4,5 as a ,b , c.
  - So if we want to rob a , then we need value of **money collected from b.withoutRobbery + c.withoutRoberry and add to money collected from a**.
  - If we dont want to rob a , then our total money collected will be **( max of b.withRobbery and b.withoutRobbery) + (max of c.withRobbery and c.withoutRobbery)**
  - we will follow this approach in post order traversal (left,right,root) i.e[1,3,4,1,5,3] in above diagram.
  - At 4 b.withRobbery = 4 and b.withoutRobbery =4
  - At 5 c.withRobbery = 5 and c.withoutRobbery =1
  - At 3 a.withRobbery = 4 + 1 + 3 = 8 and a.withoutRobbery = 4 + 5 = 9.

  ![House Robber Night](https://t3.ftcdn.net/jpg/02/66/30/28/360_F_266302849_UTM19gJVc2KWN1kSNi0nG2CgHSXlzOGK.jpg)

```js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function (root) {
  const res = dfs(root);

  return Math.max(...res);

  function dfs(node) {
    // if null node
    if (node == null) return [0, 0]; // first value is the sum of the prev node included and the second value is the sum without the prev node

    const [withPrevLeft, withoutPrevLeft] = dfs(node.left);
    const [withPrevRight, withoutPrevRight] = dfs(node.right);

    const withCurr = withoutPrevLeft + withoutPrevRight + node.val;
    const withoutCurr =
      Math.max(withPrevLeft, withoutPrevLeft) +
      Math.max(withPrevRight, withoutPrevRight);

    return [withCurr, withoutCurr];
  }
};
```

###### Time and Space Complexity

Time Complexity is **O(N)**.
Space complexity in this case is **O(1)**.
