Tree and Bitmask DP

🌳 Advanced DP: Tree and Bitmask DP

The Adventure Begins: A Tale of Clever Choices

Imagine you’re the captain of a treasure-hunting team. You have a map showing a network of islands connected by bridges (that’s our tree). On each island, there’s treasure. But here’s the catch: if you collect treasure from one island, the guards on all directly connected islands wake up and block you!

How do you maximize your treasure? That’s exactly what Tree DP solves!

And what about choosing the perfect combination from a set of items? Like picking toppings for a pizza, but you need to try ALL possible combinations quickly? That’s where Bitmask DP becomes your superpower!

🌲 Part 1: DP on Trees

What is a Tree?

Think of a family tree:

• One person at the top (the root - like great-grandparent)
• Each person has children below them
• No loops! You can’t be your own grandparent

        1 (root)
       / \
      2   3
     / \
    4   5

The Big Idea

When solving problems on trees, we think bottom-up:

1. Start from the leaves (nodes with no children)
2. Work your way up to the root
3. Each node makes decisions based on its children’s answers

Analogy: Imagine asking each family member: “What’s the best you can do?” The parent then combines children’s answers to find their best answer!

🏠 Part 2: House Robber III

The Story

You’re a clever robber in a neighborhood where houses are arranged in a tree. Each house has cash inside. Rule: If you rob a house, you CAN’T rob its directly connected houses (parent or children).

     [3]        ← House with $3
    /   \
  [2]   [3]     ← Houses with $2, $3
    \     \
    [3]   [1]   ← Houses with $3, $1

The Clever Strategy

For each house, you have TWO choices:

• ROB IT 🎭 → Take this house’s money + money from grandchildren (skip children)
• SKIP IT ❌ → Take the best from children (rob or skip each)

Java Solution

// Each node returns [notRob, rob]
public int[] helper(TreeNode node) {
    if (node == null)
        return new int[]{0, 0};

    int[] left = helper(node.left);
    int[] right = helper(node.right);

    // If we DON'T rob this house
    int notRob = Math.max(left[0], left[1])
               + Math.max(right[0], right[1]);

    // If we ROB this house
    int rob = node.val + left[0] + right[0];

    return new int[]{notRob, rob};
}

public int rob(TreeNode root) {
    int[] result = helper(root);
    return Math.max(result[0], result[1]);
}

Step-by-Step Example

     [3]
    /   \
  [4]   [5]
  / \     \
[1] [3]   [1]

Bottom-up calculation:

Answer: $9 (Rob houses 4 and 5, skip root!)

🎭 Part 3: DP with Bitmasks

What’s a Bitmask?

A bitmask is just a number that represents a set using 0s and 1s!

Think of it like light switches:

• You have 3 switches (for items A, B, C)
• Each switch is ON (1) or OFF (0)
• All combinations: 000, 001, 010, 011, 100, 101, 110, 111

Number 5 in binary = 101
Means: item 0 is ON, item 1 is OFF, item 2 is ON
       → Set = {A, C}

Why Use Bitmasks?

1. Super Fast: Checking/updating sets in O(1)
2. Memory Efficient: One integer = one set
3. Easy Iteration: Loop through all subsets easily

Key Bit Operations

// Check if item i is in set
boolean hasItem = (mask & (1 << i)) != 0;

// Add item i to set
int newMask = mask | (1 << i);

// Remove item i from set
int newMask = mask & ~(1 << i);

// Toggle item i
int newMask = mask ^ (1 << i);

// Count items in set
int count = Integer.bitCount(mask);

Visual Guide

mask = 13 = 1101 in binary

Position:  3 2 1 0
Bits:      1 1 0 1
           ↓ ↓   ↓
Items:     D C   A  → Set = {A, C, D}

🎒 Part 4: Subsets Using Bitmasks

The Power of Subsets

For a set of n items, there are 2^n subsets (including empty set).

Example: Set = {🍎, 🍌, 🍊}

Generate All Subsets in Java

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;

    // Loop through all 2^n masks
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> subset = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            // If bit i is set, include nums[i]
            if ((mask & (1 << i)) != 0) {
                subset.add(nums[i]);
            }
        }
        result.add(subset);
    }
    return result;
}

Iterate Through Submasks

Sometimes you need all submasks of a mask (subsets of a subset):

// Get all submasks of 'mask'
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // 'sub' is a submask of 'mask'
    process(sub);
}
// Don't forget the empty submask!
process(0);

Example: Submasks of 5 (101):

• 101 (5) → {A, C}
• 100 (4) → {C}
• 001 (1) → {A}
• 000 (0) → {}

🧩 Putting It Together: When to Use What?

graph TD
    A["Problem Type?"] --> B{Tree Structure?}
    B -->|Yes| C["Tree DP"]
    B -->|No| D{Small Set n≤20?}
    D -->|Yes| E["Bitmask DP"]
    D -->|No| F["Other DP"]
    C --> G["House Robber III style"]
    E --> H["Subsets/Combinations"]

Quick Decision Guide

🎯 Real-World Applications

Tree DP

• Social networks: Influence maximization
• Company hierarchy: Budget allocation
• File systems: Space optimization

Bitmask DP

• Traveling Salesman Problem (TSP)
• Job scheduling
• Game theory (choosing moves)

💡 Key Takeaways

1. Tree DP: Think bottom-up. Each node’s answer depends on children.

2. House Robber III: Track two states per node - rob or skip.

3. Bitmasks: Integers represent sets. Use bit operations for lightning-fast set manipulation.

4. Subsets: Loop 0 to 2^n - 1. Each number IS a subset!

5. Submask iteration: sub = (sub - 1) & mask magically gives all submasks.

🚀 You’re Ready!

You now understand how to:

• Solve problems on tree structures with DP
• Use the clever “rob or skip” pattern
• Represent sets as binary numbers
• Generate all subsets in one elegant loop

These techniques unlock solutions to problems that would take forever with brute force. You’re not just learning algorithms - you’re learning to think like a computer scientist!

Next step: Practice with real problems. Start simple, build up!