Bitmask and Tree DP

Every DP state so far has been a prefix, a grid cell, or a range — always built on top of an array index. Two more shapes break out of that mold entirely: a bitmask, where the state is which subset of items has been used, encoded as the bits of an integer; and a tree, where there’s no table at all — the recursive call stack itself is the DP, with each node combining answers already computed for its children.

What you’ll learn

How to represent a subset as the bits of an integer, and the three bit tricks (||, &&, 1 << i1 << i) every bitmask DP relies on.
Traveling Salesman (small n) as dp[mask][i]dp[mask][i] — the classic $O(2^n \cdot n^2)$ bitmask DP.
Why bitmask DP’s state space explodes exponentially and where its practical ceiling is.
Tree DP: post-order DFS where each call returns what its parent needs, no explicit table required.
House Robber III, Diameter of Binary Tree, and Maximum Independent Set on a general tree — three problems built on the same “combine children, then decide” shape.

Bitmask DP: state = (subset, position)

When a problem depends on which subset of up to ~20 items has been used — not their count, their specific identity — encode the subset as the bits of an integer maskmask. Bit ii set means “item ii is in the subset.” Three operations cover everything you need:

mask | (1 << i)mask | (1 << i) — add item ii to the subset.
mask & (1 << i)mask & (1 << i) — test whether item ii is already in the subset (non-zero means yes).
(1 << n) - 1(1 << n) - 1 — the “full” mask, every item included.

Traveling Salesman Problem (small n)

Visit every city exactly once, starting and ending at city 0, minimizing total travel distance. Brute force tries all (n-1)!(n-1)! orderings; bitmask DP collapses that to 2^n2^n subsets: dp[mask][i]dp[mask][i] is the cheapest way to start at city 0, visit exactly the cities in maskmask, and end at city ii.

dp[mask][i] = \min_{j \in mask,\ j \neq i} \Big( dp[mask \setminus \{i\}][j] + dist[j][i] \Big)

tsp_bitmask.py

def tsp(dist):
    n = len(dist)
    full_mask = (1 << n) - 1
    # dp[mask][i] = min cost to start at city 0, visit exactly the cities in
    # mask, and end at city i (i must be a member of mask).
    dp = [[float("inf")] * n for _ in range(1 << n)]
    dp[1][0] = 0   # mask = {0}, currently at city 0, cost so far = 0
 
    for mask in range(1 << n):
        for i in range(n):
            if dp[mask][i] == float("inf") or not (mask & (1 << i)):
                continue
            for j in range(n):
                if mask & (1 << j):
                    continue                       # j already visited in this mask
                new_mask = mask | (1 << j)
                new_cost = dp[mask][i] + dist[i][j]
                if new_cost < dp[new_mask][j]:
                    dp[new_mask][j] = new_cost
 
    # close the tour: return from the last city back to city 0
    return min(dp[full_mask][i] + dist[i][0] for i in range(1, n))
 
 
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
print(tsp(dist))   # expect 80  (tour 0 -> 1 -> 3 -> 2 -> 0)

tsp_bitmask.py

def tsp(dist):
    n = len(dist)
    full_mask = (1 << n) - 1
    # dp[mask][i] = min cost to start at city 0, visit exactly the cities in
    # mask, and end at city i (i must be a member of mask).
    dp = [[float("inf")] * n for _ in range(1 << n)]
    dp[1][0] = 0   # mask = {0}, currently at city 0, cost so far = 0
 
    for mask in range(1 << n):
        for i in range(n):
            if dp[mask][i] == float("inf") or not (mask & (1 << i)):
                continue
            for j in range(n):
                if mask & (1 << j):
                    continue                       # j already visited in this mask
                new_mask = mask | (1 << j)
                new_cost = dp[mask][i] + dist[i][j]
                if new_cost < dp[new_mask][j]:
                    dp[new_mask][j] = new_cost
 
    # close the tour: return from the last city back to city 0
    return min(dp[full_mask][i] + dist[i][0] for i in range(1, n))
 
 
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
print(tsp(dist))   # expect 80  (tour 0 -> 1 -> 3 -> 2 -> 0)

The assignment problem (match nn workers to nn tasks at minimum total cost) uses the exact same shape: dp[mask]dp[mask] is the min cost to assign tasks to the workers represented by maskmask’s set bits, trying every unused task as “the next one assigned” — one dimension instead of two, since the worker being assigned is always popcount(mask)popcount(mask).

Tree DP: the call stack is the table

A tree has no natural “index” to loop over, so tree DP skips the explicit table entirely: a post-order DFS visits every node, and each call returns whatever value(s) its parent needs to make its own decision. Because children are always resolved before their parent uses them, the recursion itself enforces the correct DP order.

House Robber III

Rob houses arranged in a binary tree; robbing a node forbids robbing its direct children (no such restriction on grandchildren). Each call returns two numbers: the best total if this node is robbed, and the best total if it’s skipped.

rob(node) = node.val + skip(left) + skip(right)

skip(node) = \max\big(rob(left), skip(left)\big) + \max\big(rob(right), skip(right)\big)

house_robber_iii.py

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def rob(root):
    def dfs(node):
        if node is None:
            return 0, 0   # (best if robbed, best if skipped) for an empty subtree
 
        left_rob, left_skip = dfs(node.left)
        right_rob, right_skip = dfs(node.right)
 
        rob_this = node.val + left_skip + right_skip       # can't rob a robbed child
        skip_this = max(left_rob, left_skip) + max(right_rob, right_skip)
 
        return rob_this, skip_this
 
    rob_root, skip_root = dfs(root)
    return max(rob_root, skip_root)
 
 
#        3
#       / \
#      2   3
#       \   \
#        3   1
tree = Node(3, Node(2, None, Node(3)), Node(3, None, Node(1)))
print(rob(tree))   # expect 7  (rob 3 + 3 + 1, skipping the two 2/3 nodes on the second level)

house_robber_iii.py

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def rob(root):
    def dfs(node):
        if node is None:
            return 0, 0   # (best if robbed, best if skipped) for an empty subtree
 
        left_rob, left_skip = dfs(node.left)
        right_rob, right_skip = dfs(node.right)
 
        rob_this = node.val + left_skip + right_skip       # can't rob a robbed child
        skip_this = max(left_rob, left_skip) + max(right_rob, right_skip)
 
        return rob_this, skip_this
 
    rob_root, skip_root = dfs(root)
    return max(rob_root, skip_root)
 
 
#        3
#       / \
#      2   3
#       \   \
#        3   1
tree = Node(3, Node(2, None, Node(3)), Node(3, None, Node(1)))
print(rob(tree))   # expect 7  (rob 3 + 3 + 1, skipping the two 2/3 nodes on the second level)

Diameter of Binary Tree

The diameter is the longest path between any two nodes, measured in edges — not necessarily through the root. Each call returns its subtree’s height, but along the way it also updates a running best for “the longest path passing through this node”:

\text{height}(node) = 1 + \max\big(\text{height}(left),\ \text{height}(right)\big)

\text{best} = \max\big(\text{best},\ \text{height}(left) + \text{height}(right)\big) \quad \text{at every node}

diameter_of_binary_tree.py

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def diameter(root):
    best = [0]   # mutable cell so the nested function can update it
 
    def height(node):
        if node is None:
            return 0
        left_h = height(node.left)
        right_h = height(node.right)
        best[0] = max(best[0], left_h + right_h)     # longest path THROUGH this node
        return 1 + max(left_h, right_h)
 
    height(root)
    return best[0]
 
 
#        1
#       / \
#      2   3
#     / \
#    4   5
tree = Node(1, Node(2, Node(4), Node(5)), Node(3))
print(diameter(tree))   # expect 3  (path 4 -> 2 -> 5, or 4 -> 2 -> 1 -> 3)

diameter_of_binary_tree.py

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def diameter(root):
    best = [0]   # mutable cell so the nested function can update it
 
    def height(node):
        if node is None:
            return 0
        left_h = height(node.left)
        right_h = height(node.right)
        best[0] = max(best[0], left_h + right_h)     # longest path THROUGH this node
        return 1 + max(left_h, right_h)
 
    height(root)
    return best[0]
 
 
#        1
#       / \
#      2   3
#     / \
#    4   5
tree = Node(1, Node(2, Node(4), Node(5)), Node(3))
print(diameter(tree))   # expect 3  (path 4 -> 2 -> 5, or 4 -> 2 -> 1 -> 3)

diagram Tree DP: DFS returns bubble up from leaves before the parent decides mermaid

  graph BT
    N4["4 (leaf: height 1)"] --> N2["2 (height 2, best updated to 1+1=2)"]
    N5["5 (leaf: height 1)"] --> N2
    N3["3 (leaf: height 1)"] --> N1["1 (height 3, best updated to 2+1=3)"]
    N2 --> N1

Binary Tree Maximum Path Sum is the same shape as diameter, but summing node values instead of counting edges — and clamping each child’s contribution at max(0, subtree_sum)max(0, subtree_sum), since a negative subtree should simply be excluded from the path rather than dragging the sum down.

Maximum Independent Set on a general tree

House Robber III generalizes cleanly to any tree given as an adjacency list: each node still returns (include, exclude)(include, exclude), but now sums over every child instead of just two.

max_independent_set_tree.py

def max_independent_set(n, edges, weight):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    def dfs(node, parent):
        include = weight[node]     # take this node -- children must be excluded
        exclude = 0                 # skip this node -- children are free either way
 
        for child in graph[node]:
            if child == parent:
                continue
            child_include, child_exclude = dfs(child, node)
            include += child_exclude
            exclude += max(child_include, child_exclude)
 
        return include, exclude
 
    include_root, exclude_root = dfs(0, -1)
    return max(include_root, exclude_root)
 
 
# tree:      0
#           / \
#          1   2
#         / \
#        3   4
edges = [(0, 1), (0, 2), (1, 3), (1, 4)]
weight = [1, 1, 1, 1, 1]
print(max_independent_set(5, edges, weight))   # expect 3  (e.g. {2, 3, 4})

max_independent_set_tree.py

def max_independent_set(n, edges, weight):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    def dfs(node, parent):
        include = weight[node]     # take this node -- children must be excluded
        exclude = 0                 # skip this node -- children are free either way
 
        for child in graph[node]:
            if child == parent:
                continue
            child_include, child_exclude = dfs(child, node)
            include += child_exclude
            exclude += max(child_include, child_exclude)
 
        return include, exclude
 
    include_root, exclude_root = dfs(0, -1)
    return max(include_root, exclude_root)
 
 
# tree:      0
#           / \
#          1   2
#         / \
#        3   4
edges = [(0, 1), (0, 2), (1, 3), (1, 4)]
weight = [1, 1, 1, 1, 1]
print(max_independent_set(5, edges, weight))   # expect 3  (e.g. {2, 3, 4})

Time and space complexity

Problem	Time	Space
Bitmask DP (TSP, assignment)	$O(2^n \cdot n^2)$	$O(2^n \cdot n)$
Tree DP (House Robber III, diameter, max independent set)	$O(n)$	$O(h)$ recursion depth

When to use it

Bitmask DP: the problem depends on which specific subset of a small number of items (roughly $n \le 20$ ) has been chosen or visited — TSP, assignment problems, “partition into K equal-sum subsets.”
Tree DP: the input is literally a tree (or reduces to one), and the answer at each node depends on combining results already computed for its children — include/exclude decisions, path sums, subtree heights.
If a “subset” problem’s nn is too large for 2^n2^n to fit in memory, look for a smaller state (a count, a sum, a boolean) instead of the whole subset — that’s usually a sign a different DP shape from earlier lessons applies instead.

Practice — real LeetCode problems

Two ways to escape the array. Tree DP replaces the index with a node and the table with the call stack, returning a tuple of states per node. Bitmask DP packs a set into an integer, which only works because the constraints keep the number of elements around 20.

LC 337 — House Robber III · Medium

Problem. The houses form a binary tree. You cannot rob two directly connected houses. Return the maximum you can take.

Constraints. 1 <= number of nodes <= 10**41 <= number of nodes <= 10**4, 0 <= node.val <= 10**40 <= node.val <= 10**4.

Examples. [3,2,3,null,3,null,1][3,2,3,null,3,null,1] gives 77 (3 + 3 + 1) · [3,4,5,1,3,null,1][3,4,5,1,3,null,1] gives 99 (4 + 5)

Editorial · approach, complexity, follow-ups

Tree DP: the recursion is the table, evaluated in post-order because a node’s answer needs its children’s.

The reason a single number per node fails is worth stating precisely. If dfsdfs returned only “the best for this subtree”, the parent could not tell whether that best plan robbed the child — and that is exactly the fact the parent needs. Returning both conditional values fixes it. This is the same idea as the taketake/skipskip pair in LC 198, lifted from a line to a tree.

Time $O(n)$ , one visit per node. Space $O(h)$ for the stack, which is $O(n)$ on a degenerate tree — and at n = 10**4n = 10**4 a path-shaped tree will blow Python’s default recursion limit of 1000. Say so; on LeetCode it happens to pass, but an interviewer may want the iterative post-order or an explicit sys.setrecursionlimitsys.setrecursionlimit.

robbedrobbed must use the children’s skippedskipped values, never their maxima. Using maxmax there is the bug that silently robs adjacent nodes.
skippedskipped takes each child’s own max independently. Skipping a node imposes no constraint on either child, and the two children never constrain each other.
(0, 0)(0, 0) for NoneNone makes the leaves work with no special case.
[4,1,null,2,null,3][4,1,null,2,null,3] is a left-leaning path 4-1-2-3, and the answer is 7 — the two ends, 4 and 3. Path-shaped trees are what catch a recurrence that quietly assumes two children.
The naive memo on (node, parent_robbed)(node, parent_robbed) also works and is a fine answer; the tuple version just needs no dictionary.

Follow-ups you should expect: “Which houses?” — return the chosen sets, or re-descend making the same comparisons. “An nn-ary tree?” — sum skippedskipped over all children for the robbed case, and sum the per-child maxima for the skipped case. “A general graph?” — maximum weight independent set, NP-hard; trees are tractable because there is exactly one path between any two nodes. “Iteratively?” — post-order with an explicit stack, or process nodes in reverse BFS order. “Binary Tree Cameras (LC 968)?” — the same tree-DP shape with three states instead of two.

LC 847 — Shortest Path Visiting All Nodes · Hard

Problem. Given an undirected connected graph as an adjacency list, return the length of the shortest walk that visits every node. You may start and stop anywhere, and may revisit nodes and edges.

Constraints. 1 <= n <= 121 <= n <= 12, the graph is connected, no self-loops or duplicate edges.

Examples. [[1,2,3],[0],[0],[0]][[1,2,3],[0],[0],[0]] gives 44 · [[1],[0,2,4],[1,3,4],[2],[1,2]][[1],[0,2,4],[1,3,4],[2],[1,2]] gives 44

Editorial · approach, complexity, follow-ups

Read the constraint first. n <= 12n <= 12 gives $2^{12} = 4096$ subsets, and $12 \times 4096 = 49152$ states — tiny. Whenever nn is around 12 to 20 and the problem is about sets, the intended solution is almost always a bitmask.

The key modelling insight is that the node alone is not a state. You may need to walk back through a node you have already visited, so visitedvisited cannot be a plain per-node flag; it is part of the state. (node, mask)(node, mask) can be reached at most once usefully, and since every edge has weight 1, BFS over that state graph gives shortest distances directly — no Dijkstra needed.

Time $O(2^n \cdot n^2)$ . Space $O(2^n \cdot n)$ .

Seeding all nn starts at distance 0 is how “start anywhere” is encoded. A single-source BFS from node 0 answers a different, harder question.
(1 << i)(1 << i) as the initial mask — you have visited your own starting node.
n = 1n = 1 must return 0: the seed state already has the full mask, and the check happens on dequeue, before any edge is walked. The [[]][[]] case verifies exactly this, and it is why the mask test belongs at the top of the loop body rather than when enqueueing.
Marking seenseen at enqueue time, not dequeue time, is what keeps the queue from blowing up with duplicates. This is standard BFS hygiene and still worth saying.
The return 0return 0 at the end is unreachable for connected input — but write it rather than falling off the function.

Follow-ups you should expect: “How is this different from Travelling Salesman?” — TSP forbids revisiting, so it is a Held-Karp DP over (mask, last)(mask, last) minimising edge weights; here revisiting is allowed, which is what makes plain BFS correct. “Weighted edges?” — Dijkstra over the same state space. “Return the walk?” — store a parent per state and walk back. ”n = 40n = 40?” — $2^{40}$ states is out of reach; that is the meet-in-the-middle or approximation regime. “Must return to the start?” — add the closing edge, and the start node must then be part of the state.

LC 968 — Binary Tree Cameras · Hard

Problem. Place cameras on tree nodes. A camera monitors its own node, its parent and its immediate children. Return the minimum number of cameras needed so every node is monitored.

Constraints. 1 <= number of nodes <= 10001 <= number of nodes <= 1000, all node values are 0.

Examples. [0,0,null,0,0][0,0,null,0,0] gives 11 · [0,0,null,0,null,0,null,null,0][0,0,null,0,null,0,null,null,0] gives 22

Editorial · approach, complexity, follow-ups

Minimum vertex cover’s cousin — a dominating set on a tree — and the tree structure is what makes a greedy bottom-up pass optimal.

The exchange argument, which is the part to say out loud: a camera on a leaf covers the leaf and its parent, while a camera on that parent covers the leaf, the parent and the parent’s parent. So moving any leaf camera up to its parent never covers less. Therefore an optimal solution exists that places cameras only when a child is otherwise exposed — which is exactly the rule the code implements. Place as late as possible, and only under duress.

The three states are the minimum information a parent needs. Two would not do: “covered” has to be split by whether a camera lives here, because a child’s camera covers the parent for free while a merely-covered child does not.

Time $O(n)$ . Space $O(h)$ .

NoneNone returns 1, not 0. If missing children counted as uncovered, every leaf would demand its own camera and you would roughly double the count.
The order of the two checks matters. Exposed children are an obligation and must be handled first; a child’s camera is only a bonus.
The root needs the final check. Every other node can be rescued by its parent; the root has none, so a state of 0 there costs one more camera.
A single node answers 1 via that root check — both children are NoneNone, which returns 1, so dfsdfs returns 0 and the root branch fires.
[0,0,0][0,0,0] — a root with two leaf children — answers 1: one camera on the root covers all three. The leaves return 0, the root is forced, and it happens to be the optimum.
self.camerasself.cameras as a counter sidesteps threading a running total through the return value. A nonlocalnonlocal variable or a list of length 1 does the same job.

Follow-ups you should expect: “Prove the greedy is optimal?” — the exchange argument above; interviewers labelling this Hard mostly want that. “As an explicit DP?” — return a triple of costs per state and minimise, which is the mechanical version and generalises to weighted nodes. “Weighted cameras?” — the greedy breaks and you need that triple. “Minimum vertex cover on a tree (a camera covers only its edges)?” — the same two-state tree DP as House Robber III. “An nn-ary tree?” — identical, with any(child == 0)any(child == 0) over the children list. “A general graph?” — dominating set is NP-hard.

LeetCode problem set

#	Problem	Difficulty	The twist
698	Partition to K Equal Sum Subsets	Medium	Bitmask DP over which elements have been assigned to a bucket so far
—	Traveling Salesman (concept) (concept)	—	The $O(2^n \cdot n^2)$ template above (a classic interview/CP concept question rather than a direct LeetCode problem)
337	House Robber III	Medium	The include/exclude tree DP above
124	Binary Tree Maximum Path Sum	Hard	Diameter’s shape, summing values with negative subtrees clamped to 0
543	Diameter of Binary Tree	Easy	The height-plus-running-max template above

Recap

Bitmask DP encodes a subset as the bits of an integer; dp[mask][i]dp[mask][i] answers “best result using exactly this subset, ending at ii” — Traveling Salesman and assignment problems share this shape.
The state space is $O(2^n)$ , so bitmask DP is only practical for roughly $n \le 20$ — know that ceiling before reaching for it.
Tree DP needs no explicit table: a post-order DFS’s return value carries whatever the parent needs, and the call stack itself enforces “children before parent.”
House Robber III, Diameter of Binary Tree, and Maximum Independent Set all share the same “combine children, then decide include vs. exclude (or the best split)” pattern.

Between prefix DP, grid/interval DP, and bitmask/tree DP, you now have the full toolkit for recognizing and solving the overwhelming majority of DP-flavored interview and competitive-programming questions — the hard part from here is just practice: spotting which shape a new problem’s state actually needs.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Bitmask and Tree DP

What you’ll learn

Bitmask DP: state = (subset, position)

Traveling Salesman Problem (small n)

Tree DP: the call stack is the table

House Robber III

Diameter of Binary Tree

Maximum Independent Set on a general tree

Time and space complexity

When to use it

Practice — real LeetCode problems

LC 337 — House Robber III · Medium

LC 847 — Shortest Path Visiting All Nodes · Hard

LC 968 — Binary Tree Cameras · Hard

LeetCode problem set

Recap

Was this page helpful?