Tree and Bitmask DP

🌳 Advanced DP: Tree and Bitmask DP

Imagine you’re a treasure hunter exploring a magical forest. Each tree holds gold, but there’s a twist: if you take treasure from a parent tree, the child trees get angry and hide their gold! And you have a magic backpack that can remember every combination of items you’ve ever collected…

🎯 What You’ll Learn

• DP on Trees - Solving problems by climbing up or down a tree structure
• House Robber III - The famous tree robbery puzzle
• DP with Bitmasks - Using binary numbers as superpowers
• Subsets using Bitmasks - Finding every possible combination

🌲 Part 1: DP on Trees

What is a Tree in Programming?

Think of a family tree! 👨‍👩‍👧‍👦

       Grandpa (1)
        /     \
    Dad (2)   Uncle (3)
    /   \        \
 You (4) Sis (5)  Cousin (6)

• Grandpa is the root (top of the tree)
• Dad and Uncle are children of Grandpa
• You, Sis, and Cousin are leaves (no children)

The Big Idea 💡

DP on Trees = Solving small problems at leaves, then combining answers as you go up!

It’s like asking everyone in your family how much candy they have:

1. First, ask the kids (leaves) - they just tell you directly
2. Then, parents add up their kids’ candy + their own
3. Finally, Grandpa knows the total!

Simple Example: Sum of All Nodes

// Each node has a value
// Find total sum of the tree

function treeSum(node) {
  // Base case: empty tree
  if (node === null) return 0;

  // DP magic: my sum = my value +
  //           left subtree + right subtree
  return node.val +
         treeSum(node.left) +
         treeSum(node.right);
}

Why this works:

• Leaves return just their value
• Parents add their value + both children’s totals
• Answer bubbles up like magic! ✨

🏠 Part 2: House Robber III

The Story

You’re a clever robber planning to steal from houses arranged like a tree. But there’s a catch: security alarms connect parent and child houses!

If you rob a house, you cannot rob its direct children (they’ll call the police!).

        House: $3
        /       \
   House: $2   House: $3
      \           \
    House: $3   House: $1

Question: What’s the maximum money you can steal?

The Trick: Two Choices Per House

For each house, you have exactly 2 options:

1. ROB it 🔓 - Take the money, skip children
2. SKIP it ⏭️ - Don’t take money, children are fair game

The Solution

function rob(root) {
  // Returns [skip, rob] for each node
  function dp(node) {
    if (!node) return [0, 0];

    // Get answers from children first
    const left = dp(node.left);
    const right = dp(node.right);

    // If I SKIP this house:
    // Take best choice from each child
    const skip = Math.max(left[0], left[1]) +
                 Math.max(right[0], right[1]);

    // If I ROB this house:
    // Must skip both children
    const robIt = node.val + left[0] + right[0];

    return [skip, robIt];
  }

  const result = dp(root);
  return Math.max(result[0], result[1]);
}

Walking Through the Example

        $3
       /   \
     $2     $3
       \      \
       $3     $1

Step 1: Start at leaves

• Bottom-left $3: [skip=0, rob=3]
• Bottom-right $1: [skip=0, rob=1]

Step 2: Middle nodes

• Node $2:
  • skip = max(0,3) = 3
  • rob = 2 + 0 = 2
  • Returns [3, 2]
• Node $3 (right):
  • skip = max(0,1) = 1
  • rob = 3 + 0 = 3
  • Returns [1, 3]

Step 3: Root $3

• skip = max(3,2) + max(1,3) = 3 + 3 = 6
• rob = 3 + 3 + 1 = 7 ✅

Answer: $7 (Rob root + both bottom leaves!)

🎭 Part 3: DP with Bitmasks

What’s a Bitmask?

A bitmask is just a number where each bit (0 or 1) represents a yes/no choice!

Think of it as a row of light switches:

Switches:  [OFF] [ON] [ON] [OFF]
Binary:      0    1    1    0
Number:           = 6

Why is This Useful?

Imagine you have 4 friends: A, B, C, D

To track who’s invited to a party:

• 0000 (0) = nobody invited 😢
• 1111 (15) = everyone invited 🎉
• 1010 (10) = A and C invited
• 0101 (5) = B and D invited

One number stores multiple yes/no answers!

Bitmask Operations (Your New Superpowers)

// Check if person i is included
function isIncluded(mask, i) {
  return (mask & (1 << i)) !== 0;
}

// Add person i to the group
function addPerson(mask, i) {
  return mask | (1 << i);
}

// Remove person i from the group
function removePerson(mask, i) {
  return mask & ~(1 << i);
}

// Toggle person i (flip their status)
function toggle(mask, i) {
  return mask ^ (1 << i);
}

Real Example: Visiting Cities

You must visit N cities exactly once (like the traveling salesman).

function minCost(distances, n) {
  // dp[mask] = min cost to visit cities in mask
  const ALL = (1 << n) - 1; // All cities visited
  const dp = new Array(1 << n).fill(Infinity);

  dp[1] = 0; // Start at city 0

  for (let mask = 1; mask <= ALL; mask++) {
    // For each current state
    for (let last = 0; last < n; last++) {
      // If we're at city 'last'
      if (!(mask & (1 << last))) continue;

      for (let next = 0; next < n; next++) {
        // Try visiting 'next' city
        if (mask & (1 << next)) continue;

        const newMask = mask | (1 << next);
        dp[newMask] = Math.min(
          dp[newMask],
          dp[mask] + distances[last][next]
        );
      }
    }
  }

  return dp[ALL];
}

🎒 Part 4: Subsets Using Bitmasks

The Magic of Subsets

Want to find ALL possible combinations of items? Bitmasks make it easy!

For 3 items [A, B, C], there are 2³ = 8 subsets:

Generating All Subsets

function generateSubsets(items) {
  const n = items.length;
  const result = [];

  // Loop through all possible masks
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];

    // Check each bit
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        subset.push(items[i]);
      }
    }

    result.push(subset);
  }

  return result;
}

// Example
console.log(generateSubsets(['🍎', '🍌', '🍊']));
// [ [], ['🍎'], ['🍌'], ['🍎','🍌'],
//   ['🍊'], ['🍎','🍊'], ['🍌','🍊'],
//   ['🍎','🍌','🍊'] ]

Subset Sum Problem

Problem: Given numbers, find if any subset sums to target.

function subsetSum(nums, target) {
  const n = nums.length;

  // Try every possible subset
  for (let mask = 0; mask < (1 << n); mask++) {
    let sum = 0;

    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        sum += nums[i];
      }
    }

    if (sum === target) return true;
  }

  return false;
}

// Example
console.log(subsetSum([3, 7, 1, 8], 11));
// true (3 + 8 = 11)

Iterating Over Subsets of a Subset

Sometimes you need all subsets of a specific mask:

function subsetsOfMask(mask) {
  const subsets = [];

  // Magic formula: iterates only subsets!
  for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
    subsets.push(sub);
  }
  subsets.push(0); // Don't forget empty set

  return subsets;
}

// For mask = 5 (binary: 101)
// Subsets: 5(101), 4(100), 1(001), 0(000)

🧠 Putting It All Together

When to Use What?

graph TD
    A["Problem Type?"] --> B{Tree Structure?}
    B -->|Yes| C["DP on Trees"]
    B -->|No| D{Need Subsets?}
    D -->|Yes| E["Bitmask DP"]
    D -->|No| F["Regular DP"]
    C --> G{Parent-Child<br>Constraint?}
    G -->|Yes| H["House Robber&lt;br&gt;Pattern"]
    G -->|No| I["Simple Tree DP"]

Key Patterns to Remember

🎉 You Made It!

You now understand:

✅ Tree DP - Solve from leaves up to root

✅ House Robber III - Track (skip, rob) for each node

✅ Bitmasks - One number = many yes/no choices

✅ Subsets - Loop from 0 to 2ⁿ-1 to try everything

Remember: These techniques are like LEGO blocks. Once you know them, you can combine them to solve amazingly complex problems!

The treasure hunter who masters both the forest (trees) and the magic backpack (bitmasks) can solve any puzzle the kingdom throws at them! 🏆