06 — Tree DP & Bitmask DP

Phase 4 | Week 28–29 | Feb 16 – Feb 22, 2027

Tree DP and bitmask DP are the two most niche patterns in this phase — but “niche” doesn’t mean rare. Tree DP covers an entire class of problems on trees where you compute answers bottom-up from leaves to root. Bitmask DP solves a specific class of subset enumeration problems that would otherwise require exponential brute force. Both have unmistakable signatures in problem statements once you know what to look for.

Part I — Tree DP

The Core Idea

A tree’s recursive structure maps naturally onto DP. Every node’s answer depends on its children’s answers. You compute bottom-up: leaves first, root last. This is just post-order traversal with state accumulation.

General structure:

def dfs(node, parent):
    dp[node] = base_value
    for child in children[node]:
        if child != parent:
            dfs(child, node)
            dp[node] = f(dp[node], dp[child])  # combine child result

The key design question is: what does dp[node] represent? Most tree DP problems require dp[node] to encode two things — “answer when this node is included” and “answer when this node is excluded” — because the parent’s decision depends on both.

Problem 1: House Robber on a Tree (LeetCode 337)

Problem: Binary tree where each node has a value. You can’t rob a node and its direct parent simultaneously. Maximize total stolen value.

Why this is interesting: The circular constraint from House Robber II now applies at every parent-child edge.

State: For each node, compute two values:

  • rob[node] = max value if we rob this node

  • skip[node] = max value if we skip this node

Transitions:

rob[node]  = node.val + skip[left] + skip[right]  # rob this, must skip children
skip[node] = max(rob[left], skip[left]) + max(rob[right], skip[right])  # skip this, children are free

Answer: max(rob[root], skip[root])

Implementation: DFS returns a tuple (rob, skip) for each node. Clean and natural.

Problem 2: Diameter of Tree via DP (LeetCode 543)

Problem: Find the diameter of a binary tree — the longest path between any two nodes.

Key insight: The longest path through a node = left_depth + right_depth. The diameter is the max of this across all nodes.

State: dp[node] = maximum depth of subtree rooted at node (longest path going downward).

Transition:

def dfs(node):
    if not node: return 0
    left  = dfs(node.left)
    right = dfs(node.right)
    diameter = max(diameter, left + right)  # update global max
    return 1 + max(left, right)             # return depth for parent

The diameter update is global; the return value is local (used by parent). This pattern — compute a local result, update a global answer — appears in many tree DP problems.

Problem 3: Binary Tree Maximum Path Sum (LeetCode 124)

Problem: Find the maximum path sum between any two nodes in a binary tree. Nodes can have negative values. The path doesn’t need to pass through the root.

Same pattern as diameter: The maximum path through a node = node.val + max_gain_left + max_gain_right.

State: dp[node] = maximum sum of a path starting at this node and going downward (not branching).

def dfs(node):
    if not node: return 0
    left_gain  = max(dfs(node.left), 0)   # discard negative contributions
    right_gain = max(dfs(node.right), 0)
    global_max = max(global_max, node.val + left_gain + right_gain)
    return node.val + max(left_gain, right_gain)  # can only extend one direction for parent

The max(..., 0) trick ignores subtrees that would reduce the sum. Critical detail.

Tree Rerooting Technique (Advanced)

Some tree DP problems ask for the answer at every node, not just the root. Example: “for each node, find the sum of distances to all other nodes.”

Naive: Run DP from every node as root. O(n²).

Rerooting:

  1. Root the tree arbitrarily. Run DFS to compute down[node] (answer considering only subtree).

  2. Run second DFS top-down. For each child, compute up[child] using the parent’s full answer minus the child’s contribution. Combine down[child] and up[child] to get the full answer at child.

This is O(n) total. The canonical problem is LeetCode 834 (Sum of Distances in Tree). It’s hard; flag it for after you’re comfortable with basic tree DP.

Part II — Bitmask DP

When Bitmask DP Applies

Trigger conditions:

  • n is small (n ≤ 20, commonly n ≤ 15 in practice)

  • Problem involves assigning, selecting, or ordering a subset of n elements

  • You need to track “which elements have been used so far” as state

Why it works: A bitmask (integer) with n bits represents all 2^n subsets of n elements. bit k is 1 if element k is included in the current subset. This lets you use an integer as a compact state.

Time complexity: O(2^n × n) is typical — iterate over all 2^n masks, do O(n) work per mask. For n = 20, that’s ~20 million operations. Acceptable.

Problem 1: Traveling Salesman Problem (TSP)

Problem: Visit all n cities exactly once, starting and ending at city 0. Minimize total distance.

State: dp[mask][i] = minimum cost to visit exactly the cities in mask, ending at city i.

Base case: dp[1 << 0][0] = 0 (only city 0 visited, at city 0, cost 0).

Transition: For each state (mask, i), try extending to an unvisited city j:

for mask in range(1, 1 << n):
    for i in range(n):
        if not (mask >> i & 1): continue  # city i not in mask, skip
        for j in range(n):
            if mask >> j & 1: continue    # city j already visited
            new_mask = mask | (1 << j)
            dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist[i][j])

Answer: min(dp[(1<<n)-1][i] + dist[i][0] for i in range(1, n)) — return to city 0 from any last city.

Space: O(2^n × n). For n = 20: 2^20 × 20 × 4 bytes ≈ 80 MB. Tight but feasible.

Problem 2: Assign Tasks to Workers (LeetCode 1125)

Problem: n workers, m tasks. Assign tasks in groups to workers. Each worker assigned one group per “day,” each group must include at least difficulty[i] workers. Maximize tasks completed.

This is a bitmask DP where the mask represents which tasks have been completed. Enumerate subsets of the remaining tasks that can be assigned to the next worker.

Pattern: Iterate over all submasks of a mask using:

sub = mask
while sub:
    # process submask `sub` of `mask`
    sub = (sub - 1) & mask

This enumerates all subsets in O(3^n) total time across all masks (each bit independently in/out/not-in-mask). Important optimization for submask enumeration.

Problem 3: Minimum XOR Sum (LeetCode 1879)

Problem: Two arrays of same length n. Assign each element of nums2 to exactly one element of nums1 (bijection). Minimize sum of XOR values.

State: dp[mask] = minimum XOR sum when mask represents which elements of nums2 have been assigned. The number of set bits in mask = the index into nums1 we’re assigning next.

dp[0] = 0
for mask in range(1 << n):
    i = bin(mask).count('1') - 1   # next index in nums1 to assign (or current)
    for j in range(n):
        if mask >> j & 1:          # j has been assigned in nums2
            prev_mask = mask ^ (1 << j)
            dp[mask] = min(dp[mask], dp[prev_mask] + (nums1[i] ^ nums2[j]))

Answer: dp[(1<<n)-1]

Bitmask DP Common Operations

# Check if bit k is set
(mask >> k) & 1

# Set bit k
mask | (1 << k)

# Clear bit k
mask & ~(1 << k)

# Toggle bit k
mask ^ (1 << k)

# Count set bits (Python)
bin(mask).count('1')   # or use popcount in C++

# Iterate over all submasks of mask
sub = mask
while sub:
    # use sub
    sub = (sub - 1) & mask

What Most Engineers Get Wrong

1. Not recognizing when n is small enough for bitmask DP. When a problem says n ≤ 15 or n ≤ 20 with no obvious polynomial algorithm, that’s almost always a bitmask DP signal. The n constraint is the hint. If you’re trying to find an O(n²) solution for n = 15 with exponential state space, you’re looking in the wrong direction.

2. Tree DP: encoding only one state per node instead of two. Many tree DP problems require tracking both “include this node” and “exclude this node” states, because the parent’s decision depends on both options. If you only track one state, your transition becomes incorrect — you’ll either force inclusion or exclusion where the parent needs flexibility.

Practice Problems

Tree DP

  1. House Robber III — LeetCode 337. The template problem. Two-state tree DP.

  2. Binary Tree Maximum Path Sum — LeetCode 124. Global max updated during DFS. Hard; expect 30-45 minutes.

Medium Bitmask DP

  1. Partition to K Equal Sum Subsets — LeetCode 698. Bitmask DP where mask tracks which elements have been used. n ≤ 16.

  2. Minimum XOR Sum of Two Arrays — LeetCode 1879. Assignment bitmask DP.

Hard Bitmask DP

  1. Shortest Path Visiting All Nodes — LeetCode 847. BFS + bitmask state. Track (node, visited_mask). Not pure DP but uses bitmask state space.

  2. Smallest Sufficient Team — LeetCode 1125. Subset cover bitmask DP. Requires careful mask iteration.