title: House Robber III
slug: house-robber-iii
difficulty: medium
leetcode_id: 337
leetcode_url: https://leetcode.com/problems/house-robber-iii/
categories:
  - trees
  - dynamic-programming
patterns:
  - slug: dfs
    is_optimal: true
  - slug: dynamic-programming
    is_optimal: false

function_signature: "def rob(root: TreeNode) -> int:"

test_cases:
  visible:
    - input: { root: [3, 2, 3, null, 3, null, 1] }
      expected: 7
    - input: { root: [3, 4, 5, 1, 3, null, 1] }
      expected: 9
  hidden:
    - input: { root: [1] }
      expected: 1
    - input: { root: [1, 2, 3] }
      expected: 5
    - input: { root: [4, 1, null, 2, null, 3] }
      expected: 7
    - input: { root: [2, 1, 3, null, 4] }
      expected: 7
    - input: { root: [0, 0, 0, 0, 0] }
      expected: 0
    - input: { root: [1, null, 2, null, 3, null, 4] }
      expected: 6

description: |
  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 realised 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*.

constraints: |
  - The number of nodes in the tree is in the range `[1, 10^4]`
  - `0 <= Node.val <= 10^4`

examples:
  - input: "root = [3,2,3,null,3,null,1]"
    output: "7"
    explanation: "Maximum amount of money the thief can rob = 3 + 3 + 1 = 7 (root and two grandchildren)."
  - input: "root = [3,4,5,1,3,null,1]"
    output: "9"
    explanation: "Maximum amount of money the thief can rob = 4 + 5 = 9 (the two children of root)."

explanation:
  intuition: |
    Picture a family tree where each person holds some cash. You want to collect as much money as possible, but there's a catch: if you take money from someone, you can't take from their direct parent or children — only from grandparents, grandchildren, or unrelated branches.

    The key insight is that at every node, you face a **binary choice**:

    - **Rob this node**: You get its value, but you *cannot* rob its children. However, you *can* rob its grandchildren (the children's children).
    - **Skip this node**: You don't get its value, but you're free to rob its children (and potentially their children too).

    Think of it like this: each node needs to report back two pieces of information to its parent — *"Here's how much you can get if you rob me, and here's how much you can get if you skip me."* The parent then uses both pieces to make its own optimal decision.

    This naturally suggests a **post-order DFS** approach: process children first, collect their "rob/skip" information, then compute the current node's optimal values.

  approach: |
    We solve this using **Tree DP with DFS**, where each node returns a pair of values: `(rob_this_node, skip_this_node)`.

    **Step 1: Define what each node returns**

    - `rob`: Maximum money if we rob this node (includes node's value, but excludes children)
    - `skip`: Maximum money if we skip this node (children are free to be robbed or skipped)

    &nbsp;

    **Step 2: Handle the base case**

    - For a `null` node (empty subtree), return `(0, 0)` — no money either way
    - This provides the termination condition for our recursion

    &nbsp;

    **Step 3: Recurse on children (post-order DFS)**

    - Call the function on `left` child, getting `(left_rob, left_skip)`
    - Call the function on `right` child, getting `(right_rob, right_skip)`
    - We now know the optimal values for both subtrees

    &nbsp;

    **Step 4: Calculate current node's values**

    - `rob_current = node.val + left_skip + right_skip`
      - If we rob this node, children must be skipped
    - `skip_current = max(left_rob, left_skip) + max(right_rob, right_skip)`
      - If we skip this node, each child independently chooses its best option

    &nbsp;

    **Step 5: Return the answer**

    - At the root, return `max(rob_root, skip_root)`
    - This gives the global maximum across all valid robbery plans

  common_pitfalls:
    - title: Naive Recursion Without Memoisation
      description: |
        A tempting approach is to write a simple recursive function:

        ```python
        def rob(node):
            if not node:
                return 0
            # Rob this node + grandchildren
            rob_this = node.val
            if node.left:
                rob_this += rob(node.left.left) + rob(node.left.right)
            if node.right:
                rob_this += rob(node.right.left) + rob(node.right.right)
            # Skip this node, rob children
            skip_this = rob(node.left) + rob(node.right)
            return max(rob_this, skip_this)
        ```

        This recalculates the same subtrees multiple times. For example, `rob(node.left)` is computed both when considering robbing the current node's grandchildren and when skipping the current node. This leads to **exponential time complexity O(2^n)** and will cause TLE.
      wrong_approach: "Simple recursion visiting same nodes repeatedly"
      correct_approach: "Return (rob, skip) pair so each node is visited exactly once"

    - title: Forgetting the Skip Option Gives Freedom
      description: |
        When you skip a node, you're not forced to rob its children — you simply have the *option* to rob them.

        The correct formula for `skip_current` is:
        ```
        skip = max(left_rob, left_skip) + max(right_rob, right_skip)
        ```

        A common mistake is writing `skip = left_rob + right_rob`, which forces robbing both children. But sometimes skipping a child yields more money (e.g., if the grandchildren have higher values).
      wrong_approach: "skip = left_rob + right_rob"
      correct_approach: "skip = max(left_rob, left_skip) + max(right_rob, right_skip)"

    - title: Confusing Tree DP with Array DP
      description: |
        Unlike House Robber I (array) where you track `dp[i-1]` and `dp[i-2]`, tree DP tracks relationships via parent-child edges, not indices.

        You can't simply apply the array recurrence `dp[i] = max(nums[i] + dp[i-2], dp[i-1])` because:
        - Trees have multiple children (not just one "previous" element)
        - The "skip two" concept becomes "skip direct link" (rob grandchildren, not `i-2`)
        - Each node can have 0, 1, or 2 children

        The pair-returning approach `(rob, skip)` is the tree analogue of the space-optimised array DP.

  key_takeaways:
    - "**Tree DP pattern**: Return multiple values (rob/skip) from recursion to avoid redundant computation"
    - "**Post-order traversal**: Process children first, then compute parent's answer from children's results"
    - "**Binary choice at each node**: Rob (take value, skip children) vs Skip (children choose freely)"
    - "**Generalises House Robber**: Same core constraint (no adjacent), different data structure (tree vs array)"

  time_complexity: "O(n). Each node is visited exactly once during the DFS traversal, and we do O(1) work per node."
  space_complexity: "O(h) where h is the tree height. The recursion stack can grow as deep as the tree. In the worst case (skewed tree), this is O(n); for a balanced tree, it's O(log n)."

solutions:
  - approach_name: Tree DP with DFS
    is_optimal: true
    code: |
      class TreeNode:
          def __init__(self, val=0, left=None, right=None):
              self.val = val
              self.left = left
              self.right = right

      def rob(root: TreeNode | None) -> int:
          def dfs(node: TreeNode | None) -> tuple[int, int]:
              # Base case: null node contributes nothing
              if not node:
                  return (0, 0)

              # Post-order: process children first
              left_rob, left_skip = dfs(node.left)
              right_rob, right_skip = dfs(node.right)

              # If we rob this node, we must skip both children
              rob_current = node.val + left_skip + right_skip

              # If we skip this node, each child chooses its best option
              skip_current = max(left_rob, left_skip) + max(right_rob, right_skip)

              return (rob_current, skip_current)

          rob_root, skip_root = dfs(root)
          return max(rob_root, skip_root)
    explanation: |
      **Time Complexity:** O(n) — Each node visited exactly once.

      **Space Complexity:** O(h) — Recursion stack depth equals tree height.

      Each node returns a pair: (max if robbed, max if skipped). The parent combines these to compute its own pair. At the root, we take the maximum of both options. This eliminates redundant computation by ensuring each subtree is evaluated exactly once.

  - approach_name: Naive Recursion (TLE)
    is_optimal: false
    code: |
      class TreeNode:
          def __init__(self, val=0, left=None, right=None):
              self.val = val
              self.left = left
              self.right = right

      def rob(root: TreeNode | None) -> int:
          if not root:
              return 0

          # Option 1: Rob this node + grandchildren
          rob_this = root.val
          if root.left:
              rob_this += rob(root.left.left) + rob(root.left.right)
          if root.right:
              rob_this += rob(root.right.left) + rob(root.right.right)

          # Option 2: Skip this node, consider children
          skip_this = rob(root.left) + rob(root.right)

          return max(rob_this, skip_this)
    explanation: |
      **Time Complexity:** O(2^n) — Exponential due to overlapping subproblems.

      **Space Complexity:** O(h) — Recursion stack depth.

      This approach correctly identifies the two choices (rob or skip) but recalculates the same subtrees multiple times. For example, `rob(root.left)` is computed both directly and indirectly through grandchildren. This causes TLE on large trees. Included to illustrate why the pair-returning approach is necessary.

  - approach_name: Recursion with Memoisation
    is_optimal: false
    code: |
      class TreeNode:
          def __init__(self, val=0, left=None, right=None):
              self.val = val
              self.left = left
              self.right = right

      def rob(root: TreeNode | None) -> int:
          memo = {}

          def helper(node: TreeNode | None) -> int:
              if not node:
                  return 0
              if node in memo:
                  return memo[node]

              # Option 1: Rob this node + grandchildren
              rob_this = node.val
              if node.left:
                  rob_this += helper(node.left.left) + helper(node.left.right)
              if node.right:
                  rob_this += helper(node.right.left) + helper(node.right.right)

              # Option 2: Skip this node, consider children
              skip_this = helper(node.left) + helper(node.right)

              memo[node] = max(rob_this, skip_this)
              return memo[node]

          return helper(root)
    explanation: |
      **Time Complexity:** O(n) — Each node computed once due to memoisation.

      **Space Complexity:** O(n) — Hash map stores result for each node, plus O(h) recursion stack.

      Adding memoisation to the naive approach fixes the exponential blowup. However, this uses O(n) extra space for the hash map, whereas the pair-returning approach achieves the same time complexity with only O(h) space. This solution is correct and efficient, but the optimal approach is more elegant.
