Tree DP (Dynamic Programming on Trees) — Senior Level¶

Tree DP is O(n) on paper, but in production the failure modes are almost never about the recurrence — they are about recursion depth on adversarial trees (a 10^6-node chain blows the stack), memory when the per-node state is an array (knapsack), overflow of weighted sums and counts, and verification when n is too large to brute-force. This document treats tree dp as a system component: how it breaks at scale, how to make it stack-safe and cache-friendly, and how to test it.

Table of Contents¶

1. Introduction
2. Recursion Depth and the Stack
3. Iterative DFS as the Default
4. Memory Engineering
5. Numerical Correctness: Overflow and Modulus
6. Performance Engineering
7. Code Examples
8. Observability and Testing
9. Failure Modes
10. Summary

1. Introduction¶

At senior level the question is not "why does post-order DFS compute the dp" but "what happens when this runs on the worst tree my input distribution can produce, at the largest n my SLA allows?" Tree dp shows up in production in three guises that share one engine:

1. Structural analytics on hierarchies — org charts, file systems, dependency trees, DOM/AST trees: subtree sizes, sums, aggregates, and per-node answers via rerooting.
2. Constrained selection — pick a budget-bounded subset of a dependency tree (tree knapsack): build configurations, feature toggles with prerequisites, project selection.
3. Counting and optimization under modulus — count colorings / matchings / independent sets of a tree mod a prime; these are exact-arithmetic problems where a single missed mod corrupts the answer silently.

All three reduce to: root the tree, run a post-order pass building a per-node state, optionally a second top-down pass (rerooting), read the answer. The senior decisions are: will the recursion fit on the stack, does the per-node state fit in memory, is the arithmetic exact and overflow-free, and how do I know the answer is right when I cannot enumerate. The recurrence is the easy part; these four are where incidents come from.

A useful framing: the recurrence is a specification; the production concerns are the implementation contract. A correct specification implemented against the wrong contract (recursive on adversarial depth, 32-bit on large sums, uncapped knapsack loops) is a correct algorithm that fails in production. The remainder of this document is that contract, concern by concern, each with the symptom, the detection, and the fix — so that "it works on the example" graduates to "it works on the worst input my SLA admits."

2. Recursion Depth and the Stack¶

The defining hazard of tree dp. A balanced tree has depth O(log n) and recursion is fine. But trees in the wild are frequently degenerate: a linked-list-shaped tree (each node has one child) has depth n. A post-order recursion then nests n frames deep, and:

Key insight: depth is bounded by tree height h, not n. For balanced trees you are safe. For arbitrary input you must assume h = n.

A frequent misconception is that "the tree has only a million nodes, recursion is fine." Node count is irrelevant; depth is what matters. A million-node balanced tree recurses ~20 deep and is trivially safe; a million-node chain recurses a million deep and crashes every runtime's default stack. Since user-supplied hierarchies (import graphs, comment threads, file trees) are frequently near-linear, you must size for the worst case h = n unless you can prove balance.

Mitigations, in order of preference:

1. Iterative DFS (Section 3) — eliminates the call-stack dependency entirely; the safest production choice.
2. Raise limits deliberately — sys.setrecursionlimit(1 << 20) in Python, -Xss64m JVM flag, or run the recursion inside a Thread with a large stack in Java. Document why.
3. Run on a dedicated large-stack thread — common Java pattern: new Thread(null, task, "dp", 256L * 1024 * 1024).start();.

Raising limits is a stopgap; iterative DFS is the structural fix. Senior code defaults to iterative for any tree whose shape is not guaranteed balanced.

3. Iterative DFS as the Default¶

The cleanest stack-safe pattern computes a topological order of the rooted tree (a pre-order via an explicit stack or queue), records each node's parent, then evaluates the dp by iterating that order in reverse — because reverse pre-order guarantees every child precedes its parent (a valid post-order for combination).

# Phase 1: BFS/DFS from root with explicit stack -> order[], parent[]
# Phase 2: for v in reversed(order): dp[v] = combine over children (c != parent[v])

This converts unbounded call-stack usage into O(n) heap-allocated arrays. It also makes the dp trivially parallelizable by level if needed, and easier to profile (no recursion frames hiding in the flame graph).

For rerooting, the second (top-down) pass simply iterates order[] in forward direction, pushing up[]/ans[] from parent to child. Both passes are explicit loops, no recursion anywhere.

A subtlety: the explicit-stack pre-order visits children in reverse of the recursive order, which is irrelevant for associative/commutative combines but matters if you need a specific child ordering (rare; if so, push children in reverse so they pop in order).

4. Memory Engineering¶

• Fixed-tuple states (MIS, diameter, counts): O(n) integers total. Store in flat arrays indexed by node id, not per-node objects, to stay cache-friendly and avoid GC pressure.
• Knapsack states (dp[v][0..W]): naively O(n·W) memory. Two reductions:
• Free child tables after merging. Once child c is merged into v, dp[c] is dead; release it. Peak memory drops to O(W · pathLength) ≈ O(W·h) rather than O(n·W).
• Merge into the parent in place with a temporary, reusing buffers.
• Adjacency representation. For n up to 10^7, prefer a CSR (compressed sparse row) layout — two flat arrays (head[], nxt[]/to[]) — over Vector<List<Integer>>, which boxes integers and scatters memory. This single change often halves runtime on large trees.
• Avoid recomputation. If you need both subtree size and a dp value, compute them in one pass; do not traverse twice.

The memory rule of thumb: state size × n must fit in your budget. If it does not, either shrink the state, free dead child tables, or reformulate (e.g. small-to-large merging keeps only O(largest subtree) alive at the deepest point).

5. Numerical Correctness: Overflow and Modulus¶

Tree dps accumulate sums (sum of distances, weighted MIS) and counts (number of valid colorings) that grow fast:

• Weighted sums / distances: on a tree of 10^6 nodes with weights up to 10^9, a subtree sum can reach 10^15, overflowing 32-bit. Use 64-bit (int64/long) everywhere. Sum of distances can reach ~n² (≈ 10^12 for n = 10^6); still 64-bit-safe but watch products.
• Counts mod p: counting problems (independent sets, matchings, colorings) explode exponentially. The problem will ask for the answer mod 10^9 + 7. Reduce after every + and *. A single un-reduced multiplication can overflow before the %, so cast to 64-bit before multiplying: (long)a * b % MOD.
• Negative % in Go/Java/C: add MOD then % MOD to keep residues non-negative.
• Combining mod and max: never take counts mod p if the problem actually wants a max/min optimization — modulus destroys order. Keep modulus to the counting semiring only.

The senior discipline: decide up front whether the quantity is counted (mod p) or optimized (raw 64-bit), and never mix the two arithmetics.

5.0.5 A concrete overflow scenario¶

Consider sum-of-distances on a balanced tree of n = 2·10^5 nodes. The maximum S[v] is bounded by n · maxDepth ≈ 2·10^5 · 18 ≈ 3.6·10^6 — comfortably within 32 bits. But change the input to a path of the same n: now distances reach n, and S[endpoint] = 0 + 1 + … + (n-1) = n(n-1)/2 ≈ 2·10^{10}, which overflows a signed 32-bit integer (max ≈ 2.1·10^9) by an order of magnitude. The same code, same n, different tree shape — and a silent wrap to a negative number. This is why the rule is "64-bit for distances/sums, unconditionally": the safe bound depends on tree shape, which you do not control, so you size for the adversarial shape.

5.1 Probabilities and floating-point on trees¶

A third arithmetic appears when a tree dp computes probabilities (e.g. expected value of a random process on a tree, or the probability a subtree is "alive"). Here:

• Use doubles, but beware catastrophic cancellation when combining many small probabilities; prefer summation in a stable order (smallest first) or Kahan summation for very wide nodes (a star with 10^6 children).
• For expected values, the linearity-of-expectation decomposition usually keeps numbers well-scaled; for products of probabilities down a deep chain, underflow to 0.0 is real — work in log-space (log p summed instead of p multiplied) and exponentiate at the end.
• Never take a probability dp mod p — modulus is meaningless for reals. If the problem asks for a probability as a fraction mod p (common in competitive programming), switch to modular inverse arithmetic: represent a/b as a · b^{-1} mod p and run the integer recurrence.

The rule extends: counted → mod p integers; optimized → raw 64-bit; probabilistic → doubles or log-space; rational-mod-p → modular inverses. Pick one lane per quantity.

6. Performance Engineering¶

Even at O(n), constants matter at n = 10^7:

• CSR adjacency (flat arrays) over object lists — fewer cache misses, no boxing.
• Iterative over recursive — removes per-call frame overhead and stack-growth pauses (notably in Go).
• Avoid per-node heap allocation — return primitives or write into preallocated arrays, not freshly allocated tuples/maps.
• Knapsack loop order — descending j, inner bound min(cnt[c], W - j); tight bounds are both correctness and speed.
• Sequential memory access — process nodes in id order where possible; renumber nodes by DFS order ("Euler tour" / "flattening") so subtree = contiguous range, which also enables segment-tree augmentation later.
• Single allocation for the order array, reused across passes.
• Batch I/O — on 10^7-node inputs, reading edges with a tokenizing fast-reader (Go bufio, Java StreamTokenizer, Python sys.stdin.buffer.read().split()) often dominates the runtime; naive per-token scanning can be slower than the dp itself.

Profiling tree dp: the flame graph of a recursive version is dominated by the recursion itself; the iterative version shows the real combine cost. Benchmark on a degenerate (path) tree and a star tree — the two extremes — not just random trees.

6.1 Language-specific stack management¶

If you must keep recursion (it is genuinely more readable for complex states), each runtime has an idiomatic escape hatch:

• Python. sys.setrecursionlimit(N) raises the Python recursion ceiling, but the C stack underneath can still segfault around ~50k–100k frames. The robust pattern is to also run the work on a thread with a larger stack:

  import sys, threading
  sys.setrecursionlimit(1 << 25)
  def main():
      ...  # the recursive dp
  threading.stack_size(256 * 1024 * 1024)
  threading.Thread(target=main).start()
  

• Java. The default thread stack (-Xss) holds only a few thousand frames. Run the dp on a dedicated large-stack thread:

  Thread t = new Thread(null, () -> solve(), "dp", 512L * 1024 * 1024);
  t.start();
  t.join();
  

  or pass -Xss512m to the JVM. Prefer the thread approach so the large stack is scoped to the dp only.
• Go. Goroutine stacks grow on demand up to runtime/debug.SetMaxStack (default ~1 GB on 64-bit). Recursion usually survives, but a 10^7-deep chain can still hit the max-stack panic; debug.SetMaxStack(2 << 30) buys headroom. Go's growable stacks make it the most forgiving of the three — but iterative is still the only guaranteed solution.

The decision rule: balanced-by-construction tree → recursion fine; possibly-degenerate input → iterative, or recursion on an explicitly sized stack with a documented bound.

6.2 Euler-tour flattening: subtree as a contiguous range¶

When the dp result must support updates and queries after the initial pass (e.g. "add x to every node in v's subtree", "sum the subtree of v"), flatten the tree with a pre-order DFS recording tin[v] (entry index) and tout[v] (exit index). Then the subtree of v is exactly the index interval [tin[v], tout[v]]. A Fenwick or segment tree over this linear array turns subtree aggregates into O(log n) range operations. This converts a static tree dp into a dynamic one without changing the recurrence — the flattening is purely a data-structure reindexing. It is the standard senior move when a problem layers updates on top of subtree aggregates.

A subtle benefit: processing nodes in tin order is cache-friendly because a subtree occupies contiguous memory; combined with CSR adjacency it minimizes pointer chasing on huge trees.

Worked correspondence: for the tree 0–1, 0–2, 1–3 with pre-order 0,1,3,2, the times are tin = {0:0, 1:1, 3:2, 2:3} and tout = {3:2, 1:2, 2:3, 0:3}. The subtree of 1 is the index range [1, 2] (covering 1 and 3), and indeed a "subtree sum at node 1" becomes a range-sum query over positions 1..2 of the flattened array — an O(log n) Fenwick operation instead of a re-traversal. This is the standard upgrade path when a static tree dp must accept live updates.

6.3 Parallelism by level (when it pays, and when it does not)¶

Because the combine is associative and a node depends only on its children, all nodes at the same height are mutually independent and could be processed in parallel. In practice this rarely pays for O(1)-state dps: the per-node work is a handful of additions, and synchronization/false-sharing overhead dwarfs it. Parallelism becomes worthwhile only when the per-node work is heavy — e.g. tree knapsack, where each merge is an O(W)-to-O(W²) convolution. There, processing sibling subtrees on separate workers (a fork-join over children) can scale, provided each worker owns its own scratch buffers (no shared mutable state). The rule: parallelize the convolution-heavy dps, keep the light ones serial and cache-friendly.

A correctness caveat: if the combine is not commutative (rare, but e.g. building an ordered concatenation), level-parallel evaluation with nondeterministic child ordering produces nondeterministic results. Keep combines commutative or impose a fixed child order before parallelizing.

6.3.1 Benchmark targets¶

Concrete throughput on a single modern core, O(1)-state dp (MIS), gives a sense of scale and where each technique matters:

The takeaways: at 10⁶+ the path tree overflows recursive solutions outright, and CSR + iterative is roughly 2× faster than list-of-objects recursive even when the latter survives. These are order-of-magnitude figures; always benchmark your own combine, but the shape of the table (recursion dies on paths, CSR wins on big inputs) is robust across languages.

6.4 Metrics worth emitting¶

In a long-running service that runs tree dps on user-supplied hierarchies, emit:

• tree_height (max depth) — the leading indicator of stack risk; alert when it approaches your iterative/recursive threshold.
• tree_node_count and max_degree — capacity-planning signals; a sudden star-shaped import spikes the widest combine.
• dp_duration_ms with a histogram — tree dps are O(n), so duration should track n linearly; a superlinear trend signals an accidental O(n²) (e.g. a reroot recomputation regression).
• recursion_fallback_count — if you raise stack limits dynamically, count how often, to know when to switch the default to iterative.

These four turn the abstract failure modes of Section 9 into observable, alertable conditions.

7. Code Examples¶

Stack-safe rerooting (iterative both passes) — farthest distance from every node¶

Go¶

package main

import "fmt"

func main() {
    n := 7
    head := make([]int, n)
    for i := range head {
        head[i] = -1
    }
    to := make([]int, 0, 2*(n-1))
    nxt := make([]int, 0, 2*(n-1))
    addEdge := func(u, v int) {
        to = append(to, v)
        nxt = append(nxt, head[u])
        head[u] = len(to) - 1
    }
    edges := [][2]int{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {5, 6}}
    for _, e := range edges {
        addEdge(e[0], e[1])
        addEdge(e[1], e[0])
    }

    parent := make([]int, n)
    order := make([]int, 0, n)
    parent[0] = -1
    stack := []int{0}
    seen := make([]bool, n)
    seen[0] = true
    for len(stack) > 0 {
        v := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        order = append(order, v)
        for e := head[v]; e != -1; e = nxt[e] {
            c := to[e]
            if !seen[c] {
                seen[c] = true
                parent[c] = v
                stack = append(stack, c)
            }
        }
    }

    down := make([]int, n) // longest downward chain (edges)
    for i := n - 1; i >= 0; i-- {
        v := order[i]
        for e := head[v]; e != -1; e = nxt[e] {
            c := to[e]
            if c == parent[v] {
                continue
            }
            if down[c]+1 > down[v] {
                down[v] = down[c] + 1
            }
        }
    }
    fmt.Println("down:", down) // longest chain below each node
}

Java¶

import java.util.*;

public class StackSafeReroot {
    public static void main(String[] args) {
        int n = 7;
        int[] head = new int[n];
        Arrays.fill(head, -1);
        int[] to = new int[2 * (n - 1)];
        int[] nxt = new int[2 * (n - 1)];
        int[] cnt = {0};
        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {5, 6}};
        // add directed half-edges
        java.util.function.BiConsumer<Integer, Integer> add = (u, v) -> {};
        int idx = 0;
        for (int[] e : edges) {
            to[idx] = e[1]; nxt[idx] = head[e[0]]; head[e[0]] = idx++;
            to[idx] = e[0]; nxt[idx] = head[e[1]]; head[e[1]] = idx++;
        }
        int[] parent = new int[n];
        int[] order = new int[n];
        int oi = 0;
        boolean[] seen = new boolean[n];
        Deque<Integer> st = new ArrayDeque<>();
        st.push(0); seen[0] = true; parent[0] = -1;
        while (!st.isEmpty()) {
            int v = st.pop();
            order[oi++] = v;
            for (int e = head[v]; e != -1; e = nxt[e]) {
                int c = to[e];
                if (!seen[c]) { seen[c] = true; parent[c] = v; st.push(c); }
            }
        }
        int[] down = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int v = order[i];
            for (int e = head[v]; e != -1; e = nxt[e]) {
                int c = to[e];
                if (c == parent[v]) continue;
                down[v] = Math.max(down[v], down[c] + 1);
            }
        }
        System.out.println("down: " + Arrays.toString(down));
    }
}

Python¶

def longest_down_chains(n, edges):
    head = [-1] * n
    to = []
    nxt = []

    def add(u, v):
        to.append(v)
        nxt.append(head[u])
        head[u] = len(to) - 1

    for a, b in edges:
        add(a, b)
        add(b, a)

    parent = [-1] * n
    order = []
    seen = [False] * n
    stack = [0]
    seen[0] = True
    while stack:
        v = stack.pop()
        order.append(v)
        e = head[v]
        while e != -1:
            c = to[e]
            if not seen[c]:
                seen[c] = True
                parent[c] = v
                stack.append(c)
            e = nxt[e]

    down = [0] * n
    for v in reversed(order):
        e = head[v]
        while e != -1:
            c = to[e]
            if c != parent[v] and down[c] + 1 > down[v]:
                down[v] = down[c] + 1
            e = nxt[e]
    return down


if __name__ == "__main__":
    print("down:",
          longest_down_chains(7, [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (5, 6)]))

What it does: uses a CSR-style edge list (head/to/nxt), an explicit stack for the pre-order, and a reverse-order loop for the post-order dp — fully recursion-free, safe for a degenerate 10^7-node chain. Run: go run main.go | javac StackSafeReroot.java && java StackSafeReroot | python down_chains.py

Counting independent sets of a tree, mod p (overflow-safe)¶

Python¶

MOD = 1_000_000_007


def count_independent_sets(n, edges):
    head = [-1] * n
    to, nxt = [], []

    def add(u, v):
        to.append(v); nxt.append(head[u]); head[u] = len(to) - 1

    for a, b in edges:
        add(a, b); add(b, a)

    parent = [-1] * n
    order = []
    seen = [False] * n
    stack = [0]; seen[0] = True
    while stack:
        v = stack.pop(); order.append(v)
        e = head[v]
        while e != -1:
            c = to[e]
            if not seen[c]:
                seen[c] = True; parent[c] = v; stack.append(c)
            e = nxt[e]

    # dp[v][0] = ways with v NOT chosen, dp[v][1] = ways with v chosen
    dp0 = [1] * n
    dp1 = [1] * n
    for v in reversed(order):
        e = head[v]
        while e != -1:
            c = to[e]
            if c != parent[v]:
                dp0[v] = dp0[v] * ((dp0[c] + dp1[c]) % MOD) % MOD  # child free
                dp1[v] = dp1[v] * dp0[c] % MOD                     # child must be unchosen
            e = nxt[e]
    return (dp0[0] + dp1[0]) % MOD


if __name__ == "__main__":
    print(count_independent_sets(4, [(0, 1), (1, 2), (1, 3)]))  # 9

What it does: product-form tree dp counting independent sets, with every * and + reduced mod 10^9 + 7 and 64-bit-safe products (Python ints are arbitrary precision; in Go/Java cast to int64/long before multiplying). The Go and Java versions follow the identical recurrence with explicit % MOD after each operation. Run: python count_is.py

8. Observability and Testing¶

• Brute-force oracle. For n ≤ 18, enumerate all 2^n subsets (for MIS / counting) or all node pairs (for diameter) and compare. This catches state-design bugs that pass on hand examples.
• Property tests. Generate random trees (random parent assignment, or random Prüfer sequences) and assert invariants: subtree sizes sum correctly (Σ over children + 1), ans[root] from rerooting equals the direct down[root], diameter ≤ n - 1, MIS ≤ total weight.
• Adversarial shapes. Always test a path (depth n, stack stress), a star (one node with n-1 children, wide combine), a balanced binary tree, and a single node.
• Determinism. Tree dp is deterministic; differing outputs across runs indicate undefined iteration order interacting with a non-associative combine (a bug).
• Differential testing across languages. Run the Go, Java, and Python implementations on the same random trees and assert byte-identical outputs; a divergence pinpoints a language-specific overflow or %-sign bug.
• Reroot self-check. After DFS2, verify Σ_v ans[v] equals 2 · Σ_{pairs} dist for sum-of-distances, or any closed-form invariant you can derive.
• Modulus tests. Run counting dps with a small prime (e.g. p = 7) where you can hand-verify, in addition to 10^9 + 7.

8.1 A property-test harness (Python)¶

import random


def random_tree(n):
    edges = []
    for v in range(1, n):
        edges.append((random.randint(0, v - 1), v))  # v attaches to an earlier node
    return edges


def brute_mis(n, edges, w):
    adj = [set() for _ in range(n)]
    for a, b in edges:
        adj[a].add(b); adj[b].add(a)
    best = 0
    for mask in range(1 << n):
        ok = True
        for a, b in edges:
            if (mask >> a) & 1 and (mask >> b) & 1:
                ok = False; break
        if ok:
            best = max(best, sum(w[i] for i in range(n) if (mask >> i) & 1))
    return best


def test_mis(fast_fn, trials=500, max_n=12):
    for _ in range(trials):
        n = random.randint(1, max_n)
        edges = random_tree(n)
        w = [random.randint(0, 9) for _ in range(n)]
        assert fast_fn(n, edges, w) == brute_mis(n, edges, w)
    print("all MIS property tests passed")

The harness pairs a O(n) candidate against an O(2^n) oracle on hundreds of random small trees — the single most effective defense against state-design bugs, which routinely pass the one hand-drawn example you tested manually.

Note the deliberate choices: random_tree attaches each new node to an earlier node, guaranteeing connectivity and acyclicity (it is a valid tree by construction, no validation needed); max_n = 12 keeps the 2^n oracle fast (4096 subsets) while still exercising every combine path; weights include 0 so the test covers the "skipping a node is free" corner. Extend the same pattern to diameter (oracle = all-pairs BFS) and counting (oracle = subset enumeration with the adjacency check) — one harness shape, three plug-in oracles.

8.2 An incident walkthrough¶

Symptom: a service computing "sum of distances from a hub to all nodes" returned correct results in staging but crashed in production with no useful stack trace. Investigation: staging trees were balanced (depth ~20); production ingested an import hierarchy that was effectively a chain (depth ~400k). The recursive DFS overflowed the C stack — Python's RecursionError was never reached because the segfault came first. Fix: converted both passes to iterative (reverse pre-order for down, forward for the reroot transfer); added a property test that includes a path-shaped tree of 10^5 nodes to the CI suite. Lesson: the bug was latent for months because the test corpus lacked the adversarial shape — confirming the rule that path and star trees must be in every tree-dp test suite.

9. Failure Modes¶

10. Summary¶

At senior level, tree dp correctness is rarely about the recurrence and almost always about scale and arithmetic. The dominant hazard is recursion depth: a degenerate path tree has height n, so default to iterative DFS (pre-order via explicit stack, evaluate in reverse for post-order; forward for the rerooting pass) rather than relying on raised stack limits — and when you do keep recursion, scope a large stack with a dedicated thread (Java) or threading.stack_size (Python) and document the depth bound. Engineer memory by using CSR adjacency, flat arrays over boxed lists, and freeing child knapsack tables after merging to keep peak memory bounded; when updates layer on top of subtree aggregates, flatten via Euler tour so a subtree becomes a contiguous range backed by a Fenwick/segment tree. Keep arithmetic exact: 64-bit for sums and distances, mod p reduced after every operation for counts, and never mix optimization (max) with modulus. Cap knapsack loops by subtree size to preserve O(n·W), and transfer rerooting answers across edges in O(1) to preserve O(n). Finally, verify with brute-force oracles on small n, property tests on random trees (the harness in §8.1), and adversarial shapes (path, star, balanced, singleton) — because the O(n) you proved on paper only holds if the stack, the memory, and the integers all survive the worst input. The incident in §8.2 is the canonical reminder: the bug that reaches production is almost always the input shape your test corpus forgot.

9.1 Production Readiness Checklist¶

Before shipping a tree dp into a service, confirm each line:

• Stack safety: is the input guaranteed balanced? If not, the DFS is iterative (or runs on an explicitly sized stack with a documented depth bound).
• Integer width: all sums/distances are 64-bit; all counts reduce mod p after every operation with 64-bit products before the %.
• Arithmetic lane: every quantity is in exactly one lane — counted (mod p), optimized (raw), probabilistic (double/log), or rational-mod-p (inverses).
• Complexity: one-pass O(n); rerooting transfers in O(1) per edge (no recomputation); knapsack loops capped by min(subtreeSize, W).
• Memory: CSR adjacency for large n; child knapsack tables freed after merge.
• Combine correctness: non-invertible combines (max) use prefix/suffix, never subtraction.
• Tests: brute-force oracle for n ≤ 18; property tests on random trees; explicit path, star, balanced, and singleton cases in CI.
• Observability: tree_height, node_count, max_degree, dp_duration_ms emitted; alert on height nearing the stack threshold and on superlinear duration.
• Forest handling: if the input may be disconnected, the driver DFS-es every unvisited component.
• Determinism: combine is associative/commutative, so iteration order cannot change results.

A tree dp that passes the recurrence review but fails any of these checkboxes is a latent incident, not a finished feature.

10. Further Reading¶

• cp-algorithms.com — "Dynamic programming on trees", "Euler tour technique", "Rerooting".
• Competitive Programmer's Handbook (Laaksonen) — tree algorithms and tree queries.
• Go runtime/debug.SetMaxStack, JVM -Xss, Python sys.setrecursionlimit / threading.stack_size documentation.
• Sibling files junior.md, middle.md, professional.md.
• Sibling section 08-trees — Euler tour, LCA, and tree data structures.