vault

Rerooting DP

22 min read

Rerooting DP

Rerooting DP (also called all-roots tree DP or the second-pass technique) is the standard trick for computing the answer-at-every-node of a tree problem in O(n) total, rather than the naive O(n²) of running an independent Tree DP from each of the n possible roots. The technique pairs two DFS traversals: a first pull pass that fixes an arbitrary root and computes, for every node, the answer for its subtree under that root; and a second push pass that walks from the root downward, exploiting the fact that “moving the root from u to its neighbor v” changes the tree’s shape in a very local way — exactly two subtrees swap roles. By combining the precomputed pull-pass values with this local update rule, each node’s “global” answer (answer when it is the root) can be derived in O(1) from its parent’s, yielding O(n) overall. The canonical example is Sum of Distances in Tree (LeetCode 834): given a tree of n nodes, output for every v the sum of distances from v to every other node. A naive solution runs BFS from each node — O(n²) — but rerooting solves it in O(n). The technique generalizes: any tree-DP whose state factors as a commutative monoid over neighbors (sum, max, count, etc.) can be re-rooted, often by pre-computing prefix-and-suffix aggregates over each node’s children. Rerooting is one of the most reusable tree algorithms in competitive programming and a frequent source of “ohh that’s how” moments in interviews.

1. Intuition — “Move the Root by One Edge”

Imagine the tree rooted at some node u. We have, for every node v, the answer that v’s subtree contributes assuming the tree is rooted at u. Call this down(v) (the “downward” or “subtree” answer).

Now suppose we want the answer with the root re-located at v, where v is a neighbor of u. The key observation: the only thing that changes is the edge between u and v. From v’s perspective:

  • The “subtree below v” grows — it now contains everything except v’s old subtree, namely all of u’s side of the tree minus v’s old subtree.
  • The “subtree below u” shrinks — it loses v’s old subtree.

Diagrammatically, before and after, only two subtrees swap which side of the u–v edge they belong to:

Before (root = u):                  After (root = v):

          u                                 v
         / \                               / \
        A   v                             B   u
            |                                 / \
            B                                A   ...

The trick: if we precompute down(v) for every v (one DFS), and we know how to combine and uncombine a child’s contribution from the parent’s answer (often a simple add/subtract for sums or pop/push for maxes), then we can derive answer(v) from answer(u) in O(1) per edge. A second DFS, walking root-to-leaves, propagates the global answer downward. Total: O(n) for both passes.

A real-world analogy: imagine you are an employee of a hierarchical company and want to know the total commute distance from your office to every other office, summed over all employees. The naive way is to compute the routes from your office to every other office. The smart way: someone above you (your manager) already computed this answer for their office. To convert it to your answer: every employee in your subtree just got 1 unit closer (you are below your manager, so paths to them are shorter by 1), and every employee outside your subtree just got 1 unit farther. If you know how many people are in your subtree (a precomputed subtree size), you can update your answer from your manager’s in O(1). The whole company’s data is computed in two passes — top-down sizing, then top-down rerooting — over the org chart.

2. Worked Example — Sum of Distances in Tree (LC 834)

The most-cited rerooting problem. Given an undirected tree on n nodes, define f(v) = Σ_{u ≠ v} dist(u, v) (sum of distances from v to all other nodes). Output f(v) for every v.

Naive solution: BFS from each node, O(n²). Rerooting solves it in O(n).

2.1 Setup

Pick an arbitrary root, say node 0. Compute two arrays:

  • count[v] = number of nodes in the subtree of v (the subtree-size in the rooted tree). Note count[0] = n.
  • down[v] = sum of distances from v to every node in v’s subtree.

Both can be computed by a single post-order DFS:

count[v] = 1 + Σ_{c : child of v} count[c]
down[v]  = Σ_{c : child of v} (down[c] + count[c])

The + count[c] term in down[v] accounts for the fact that every node in c’s subtree is one edge farther from v than from c.

2.2 The Reroot Step

We claim that for any edge (u, v) where v is a child of u in our rooted tree, the global answers satisfy:

f(v) = f(u) − count[v] + (n − count[v])
     = f(u) + n − 2 · count[v]

Symbol-by-symbol derivation. When we move the root from u to v:

  • Every node inside v’s subtree (there are count[v] of them, including v itself) gets one edge closer to the root → total decrease count[v].
  • Every node outside v’s subtree (there are n − count[v] of them, including u) gets one edge farther from the root → total increase n − count[v].

Net change: (n − count[v]) − count[v] = n − 2 · count[v]. So f(v) = f(u) + n − 2 · count[v].

This O(1) update is the heart of rerooting. With f(0) computed from the down-pass plus contributions from the rest of the tree (which for the root is the whole tree, so f(0) = down[0]), we propagate to children.

2.3 Tiny Worked Trace

Tree on n = 6 nodes, edges: (0,1), (0,2), (2,3), (2,4), (2,5). Visualized:

         0
        / \
       1   2
          /|\
         3 4 5

Pull pass (rooted at 0, post-order DFS):

Nodecountdown
1 (leaf)10
3 (leaf)10
4 (leaf)10
5 (leaf)10
21 + 1 + 1 + 1 = 4(0+1)+(0+1)+(0+1) = 3
01 + 1 + 4 = 6(0+1)+(3+4) = 1 + 7 = 8

So f(0) = down[0] = 8. Quick sanity: distances from 0 are 0→1:1, 0→2:1, 0→3:2, 0→4:2, 0→5:2 → sum 1+1+2+2+2 = 8. ✓

Push pass (rooted answer propagation, pre-order DFS):

  • f(1) = f(0) + 6 − 2·count[1] = 8 + 6 − 2 = 12. Sanity: distances from 1 are 1→0:1, 1→2:2, 1→3:3, 1→4:3, 1→5:3 → 1+2+3+3+3 = 12. ✓
  • f(2) = f(0) + 6 − 2·count[2] = 8 + 6 − 8 = 6. Sanity: distances from 2 are 2→0:1, 2→1:2, 2→3:1, 2→4:1, 2→5:1 → 1+2+1+1+1 = 6. ✓
  • f(3) = f(2) + 6 − 2·count[3] = 6 + 6 − 2 = 10. Sanity: distances from 3: 3→2:1, 3→0:2, 3→1:3, 3→4:2, 3→5:2 → 1+2+3+2+2 = 10. ✓
  • f(4) = f(2) + 6 − 2·count[4] = 6 + 6 − 2 = 10. Symmetric.
  • f(5) = f(2) + 6 − 2·count[5] = 6 + 6 − 2 = 10. Symmetric.

Final: f = [8, 12, 6, 10, 10, 10]. The push pass touched each edge once → O(n).

The two passes are completely separate: pull populates count and down; push converts down (which is “subtree” answer) to f (the “rooted-at-this-node” answer) via the O(1) reroot update.

3. The Generic Rerooting Recipe

For a problem of the form “compute g(v) for every v, where g(v) is some aggregate over the whole tree as if v were the root”:

  1. Pull pass (post-order DFS, root anywhere). Compute down[v] = the partial answer using only v’s subtree (v is the root of its own subtree).

  2. Reroot transition. Derive a formula g(child) = update(g(parent), down[child], down[parent], structural_quantities) that, given g(parent) and the locally available down values, produces g(child) in O(1).

  3. Push pass (pre-order DFS). Set g(root) = down[root] (or whatever the root’s full answer is). Then for each child, apply the update formula.

The hardest step is (2). It usually requires unrolling “what changes when we slide the root one edge.” For monoidal aggregates with invertible combine operations (sum, XOR, count), the update is straightforward: subtract the child’s contribution from the parent’s aggregate, then add the parent’s adjusted contribution. For non-invertible aggregates (max, min, product mod prime, etc.), you typically need prefix-and-suffix aggregates over each node’s children list, so you can recover the “answer if we exclude the i-th child” in O(1) per child.

3.1 Prefix-Suffix Aggregate Trick (for max, min, etc.)

If a node u has children c_1, c_2, ..., c_d, and the aggregate is max(a_1, a_2, ..., a_d) where a_i = down[c_i] + ..., then to “answer at u excluding child c_k” we need max over all a_i except a_k. Compute:

  • prefix_max[k] = max(a_1, ..., a_{k-1})
  • suffix_max[k] = max(a_{k+1}, ..., a_d)
  • Answer excluding c_k = max(prefix_max[k], suffix_max[k])

Total time per node: O(d). Total across the tree: O(n) because Σ d = 2(n − 1) (handshake lemma). The trick generalizes to any associative operation.

4. Pseudocode

RerootingDP(tree, n):
    adj := adjacency list of tree (undirected, n nodes)
    down := array of size n
    count := array of size n             # subtree sizes (or other helper data)
    answer := array of size n             # final per-root answers

    # Pull pass: post-order DFS from arbitrary root (0)
    function pull(u, parent):
        count[u] := 1
        down[u] := 0
        for v in adj[u]:
            if v == parent: continue
            pull(v, u)
            count[u] += count[v]
            down[u]  += down[v] + count[v]    # problem-specific transition
    pull(0, -1)

    # Push pass: pre-order DFS, propagate global answer downward
    answer[0] := down[0]
    function push(u, parent):
        for v in adj[u]:
            if v == parent: continue
            answer[v] := answer[u] + n - 2 * count[v]    # problem-specific reroot update
            push(v, u)
    push(0, -1)

    return answer

The two functions are dual: pull computes “answer for u’s subtree assuming root 0”; push converts these into “answer for the tree assuming root u” using the parent’s already-known global answer.

5. Python Implementation — LC 834

from collections import defaultdict
import sys
 
def sumOfDistancesInTree(n: int, edges: list[list[int]]) -> list[int]:
    sys.setrecursionlimit(10**5)
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
 
    count = [1] * n          # subtree sizes (rooted at 0)
    down  = [0] * n          # sum of distances within v's subtree
    answer = [0] * n         # final answer for each root
 
    # Pass 1: post-order DFS — compute count[v] and down[v]
    def pull(u, parent):
        for v in adj[u]:
            if v == parent: continue
            pull(v, u)
            count[u] += count[v]
            down[u]  += down[v] + count[v]
    pull(0, -1)
 
    # Pass 2: pre-order DFS — propagate global answer downward
    answer[0] = down[0]
    def push(u, parent):
        for v in adj[u]:
            if v == parent: continue
            answer[v] = answer[u] + n - 2 * count[v]
            push(v, u)
    push(0, -1)
    return answer
 
 
# Example
edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
print(sumOfDistancesInTree(6, edges))    # [8, 12, 6, 10, 10, 10]

The two-pass structure is unmistakable. Each pass is a single recursion of depth at most O(h) where h is the tree height (worst case n for a path graph; balanced trees have h = O(log n)). For Python, raise the recursion limit; for very deep trees, an iterative explicit-stack DFS is safer.

5.1 Iterative Form (for Recursion-Limit Safety)

def sumOfDistancesInTree_iter(n: int, edges: list[list[int]]) -> list[int]:
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
 
    parent = [-1] * n
    order = []                # BFS/DFS order for pull-pass post-order
    stack = [0]
    visited = [False] * n
    visited[0] = True
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                stack.append(v)
 
    count = [1] * n
    down  = [0] * n
    # Process in reverse to ensure children before parents (post-order)
    for u in reversed(order):
        p = parent[u]
        if p != -1:
            count[p] += count[u]
            down[p]  += down[u] + count[u]
 
    answer = [0] * n
    answer[0] = down[0]
    for u in order:           # pre-order
        for v in adj[u]:
            if v != parent[u] and parent[v] == u:
                answer[v] = answer[u] + n - 2 * count[v]
    return answer

This avoids recursion entirely; useful for n > 10^4 on Python.

6. Worked Example — Tree With Maximum Distance From Each Node (Tree Diameter Variant)

A different aggregate: for each v, output max_u dist(u, v) (the eccentricity of v). Naive: BFS from each node, O(n²). Rerooting: O(n).

6.1 The Subtle Twist — Non-Invertible Aggregate

max is not invertible: knowing max(a_1, ..., a_d) = m does not let you recover max over {a_1, ..., a_d} \ {a_k}. So we cannot simply subtract.

Solution: prefix-and-suffix max over each node’s children. For node u with children c_1, ..., c_d:

  • pref_max[k] = max(down[c_i] + 1 : i ≤ k)
  • suff_max[k] = max(down[c_i] + 1 : i ≥ k)

Then “max distance from u going down, excluding child c_k’s subtree” = max(pref_max[k-1], suff_max[k+1]).

When rerooting from u to child c_k, the new “outside” subtree (from c_k’s perspective) consists of:

  • u itself + the rest of u’s descendants except c_k’s subtree, with distances at most 1 + max(pref_max[k-1], suff_max[k+1]).
  • The “outside” part above u — also the parent’s already-computed answer, with +1 to account for the edge (u → c_k) traveling outward.

The detailed transition is more verbose than LC 834 but follows the same shape: pull pass computes down[v]; push pass propagates up[v] (the answer outside v’s subtree); final eccentricity(v) = max(down[v], up[v]).

6.2 Implementation Sketch

def tree_eccentricities(n, edges):
    adj = build_adj(edges, n)
    down = [0] * n        # max depth in v's subtree
    up = [0] * n          # max distance from v upward through parent
 
    def pull(u, parent):
        max_depth = 0
        for v in adj[u]:
            if v == parent: continue
            pull(v, u)
            max_depth = max(max_depth, down[v] + 1)
        down[u] = max_depth
 
    def push(u, parent):
        # Collect (neighbor, contribution) pairs
        entries = [(v, down[v] + 1) for v in adj[u] if v != parent]
        # Add parent's contribution
        if parent != -1:
            entries.append((parent, up[u] + 1))
        # Sort by contribution descending; need top-2 to handle "exclude self" lookups
        entries.sort(key=lambda x: -x[1])
        for v, _ in entries:
            if v == parent: continue
            # When rerooting to v, the "outside" answer is the best of u's other paths
            best_excluding_v = entries[0][1] if entries[0][0] != v else (entries[1][1] if len(entries) > 1 else 0)
            up[v] = best_excluding_v
            push(v, u)
 
    pull(0, -1)
    push(0, -1)
    return [max(down[v], up[v]) for v in range(n)]

The “top-2 trick” — track the two largest contributions, so excluding any one still gives a valid answer in O(1) — is a common optimization equivalent to prefix-suffix max for this specific aggregate.

7. Comparison with Tree DP

AspectPlain Tree DPRerooting DP
GoalSingle answer for the tree (one root)Answer for every node as root
PassesOne DFSTwo DFS (pull + push)
State at each nodedp[v] for v’s subtreedown[v] + up[v] (or one global answer[v])
ComplexityO(n)O(n) (achieves what naive O(n²) does)
Common difficulty”What is the right state?”Same, plus “what changes when root moves?”
ExamplesLC 543 (Diameter), LC 124 (Max Path Sum), LC 337 (House Robber III)LC 834 (Sum of Distances), LC 310 (Min Height Trees), LC 2581 (Count Visited Nodes)

Tree DP is the foundation; rerooting is the doubling-up that gives you per-node answers without doubling the asymptotics. The intellectual leap is recognizing that “answer at v” decomposes into “answer in v’s subtree” + “answer above v”, and that the latter can be derived from v’s parent’s answer in O(1).

8. Diagram — The Reroot Transition

flowchart LR
    subgraph Before["Before: root at u"]
        U1((u)) --- V1((v))
        U1 --- A1[(other<br/>subtree A)]
        V1 --- B1[(v's subtree B,<br/>size = count[v])]
    end
    subgraph After["After: root at v"]
        V2((v)) --- U2((u))
        V2 --- B2[(B<br/>now still v's subtree but<br/>"down" from v's POV)]
        U2 --- A2[(A + everything else,<br/>now hanging off u<br/>which hangs off v)]
    end

What this diagram shows. The left pane shows the tree rooted at u, with the edge u–v separating two parts: B (everything in v’s subtree, including v) and the rest (everything else, including u and the subtree A). The right pane re-roots at v. The single edge u–v flips orientation: previously v was a child of u; now u is a child of v. As a consequence, B is still “below” v (no change), but A + everything-attached-to-u is now also “below” v because u itself is below v. The total set of nodes is the same; only the rooting of the partition changes. For aggregates like distance sums, this means count[v] nodes got closer to the root (they were 1 edge below u-as-root via v, now they’re 0 edges below v-as-root) and n − count[v] nodes got farther. For aggregates like max distance downward, the “outside” half (which wasn’t a subtree before) becomes accessible as a single “child subtree” in the rerooted view, which is why we need a precomputed up[u] to know its answer. The whole rerooting machinery is the bookkeeping needed to go from this picture’s left pane to its right pane in O(1) per edge.

9. Common Interview Problems

LC #ProblemAggregateNotes
834Sum of Distances in TreesumCanonical rerooting; O(n) solution
310Minimum Height Treesmax depth from each nodeOutput centers (1 or 2 nodes with smallest eccentricity); also solvable by leaf-pruning
2581Count Visited Nodes in a Directed GraphmixedDirected; cycle detection + rerooting on tree component
1245Tree Diameter (k-ary)max pathSolvable by 2-BFS or rerooting
1129Shortest Path with Alternating Colorsbicolored BFSNot rerooting but tree-traversal cousin
1483Kth Ancestor in Treebinary liftingDifferent technique, but same “compute for all roots” feel
968Binary Tree Camerasgreedy + tree DPPlain tree DP, included as contrast
1444Number of Ways of Cutting a Pizzanot tree, included for warningPizza is a grid, NOT a tree — be careful

The recognition signal: “compute X for every node where X depends on the entire tree from that node’s perspective.” If the question asks for a single value (one root), plain Tree DP suffices.

10. Pitfalls

10.1 Forgetting That the Tree Is Undirected

Trees in interview problems are usually given as edge lists with no specified root. The DFS must track the parent to avoid revisiting it. Off-by-one in if v == parent: continue is the most common bug.

10.2 Wrong Reroot Update Formula

The formula f(v) = f(u) + n - 2 · count[v] is specific to sum of distances. For other problems, the update is different — sometimes additive, sometimes multiplicative, sometimes requires the prefix-suffix aggregates. Always derive the formula symbol-by-symbol; don’t copy from a different problem.

10.3 Confusing count[v] Before vs After Rerooting

After rerooting at v, the “subtree size of v” is n (the whole tree), not the original count[v]. The reroot formulas use the original count[v] (computed under the arbitrary root) because they describe what changes when we move from u to v. Don’t update count[v] during the push pass.

10.4 Trying to Reroot Non-Decomposable Aggregates

Not every tree-DP can be re-rooted. The aggregate must factor over neighbors as a (commutative monoid) combine, and you must be able to either (a) invert the contribution of one child, or (b) precompute prefix/suffix aggregates. If the aggregate is “the LCA of two specific nodes” or anything else with non-local dependencies, rerooting may not apply directly.

10.5 Recursion Depth on Long Paths

A path-shaped tree (caterpillar with spine of length n) has recursion depth n. Python’s default 1000-frame limit is hit at n > 1000. Always sys.setrecursionlimit(10**5) for tree problems on inputs of this scale, or convert to iterative DFS.

10.6 Mutable State in the Pull Pass

If your count or down arrays are populated during the pull pass via +=, ensure they’re zero-initialized (or 1-initialized for sizes). Forgetting initialization is silent and produces wrong but plausible-looking answers.

10.7 Not Recognizing Symmetry

Some “rerooting” problems have additional symmetry that admits an even simpler solution. LC 310 (Min Height Trees) is solvable by leaf-pruning (“remove all leaves repeatedly; the last 1 or 2 nodes are the centers”) in O(n) without two-pass DP. Always sanity-check whether a simpler structural argument exists.

10.8 Top-Down Push Pass with Stale State

The push pass must read the parent’s already-rerooted answer, then derive the child’s. If you accidentally update the parent during the child’s computation, you’ll cascade errors. Standard trap when the recursion is written incorrectly.

10.9 Forgetting the +1 Edge in Distance Aggregations

down[v] += down[c] + count[c] not down[v] += down[c]. The + count[c] term accounts for the edge (v, c) adding 1 to every distance from v to a node in c’s subtree. Forgetting this term silently undercounts.

10.10 Mixing Up down[v] and f(v)

down[v] is “answer in v’s subtree under the arbitrary root”; f(v) is “answer with v as the root”. These are different quantities for non-root nodes. Many implementations conflate them in code or comments and produce off-by-one bugs.

11. Variants and Extensions

11.1 Weighted Edges

If edges have weights, replace + 1 in the distance accumulator with + w(edge). The reroot formula generalizes: when moving from u to v across edge of weight w, the inside-subtree gets closer by w (decrease count[v] · w) and the outside farther by w (increase (n − count[v]) · w). Net change (n − 2 · count[v]) · w.

11.2 Sum-of-Squares of Distances

The aggregate Σ dist(u, v)² is harder because squaring is non-linear in distance. The reroot formula requires tracking both the sum-of-distances and the count separately; the new sum-of-squares involves (d + Δ)² expansion. Doable but messier.

11.3 Diameter via Rerooting

The tree diameter (LC 543, generalized to k-ary) can be computed by rerooting: for each node v, the longest path through v is (top_down_subtree) + (top_down_outside) + .... In practice, the Tree Diameter note shows a simpler 2-DFS algorithm (find a farthest node a from any start, then find the farthest node b from a; dist(a, b) is the diameter) which is O(n) without the rerooting machinery. Rerooting is the more general framework but overkill for plain diameter.

11.4 Multi-Aggregate Rerooting

Some problems require computing several quantities per node (e.g., both sum-of-distances and max-distance and count-in-subtree). Each is a separate rerooting, but they share the two-pass structure and most of the bookkeeping. Code organization with a “rerooting helper” class is a good pattern.

11.5 Trees with Updates

If edges or node values change between queries, rerooting needs to be re-run from scratch — the technique is fundamentally a batch algorithm. For dynamic trees, use Heavy-Light Decomposition or link-cut trees instead.

12. Open Questions

  • Is there a clean classification of “rerootable” aggregates? Aggregates over a tree’s “neighborhood” that decompose into a commutative monoid certainly work; aggregates that depend on a path in the tree (like LCA-anchored quantities) typically don’t. A formal characterization might exist in the algebraic-DP literature.
  • Can rerooting be combined with Heavy-Light Decomposition for tree problems with updates? The two techniques are complementary in flavor; production-grade competitive-programming code sometimes blends them, but the clean theoretical story is unclear.
  • Is rerooting a special case of the sum-product algorithm on trees (belief propagation)? The two-pass structure is suspiciously similar — pull-then-push corresponds to leaves-to-root then root-to-leaves message passing in factor graphs. The precise correspondence is, as far as I know, folklore but not formally documented.

12.1 A Precise Statement of the O(n) Bound

It is worth being exact about why rerooting is linear, because the loose claim “every rerooting problem is O(n)” hides the actual mechanism. The precise statement has two cases, and both are corroborated by the standard treatments (cp-algorithms tree painting, USACO Guide “Solving For All Roots”):

  1. Invertible combine, O(1) reroot update. When the per-neighbor aggregate is a commutative group operation — one with an inverse, such as sum, XOR, or counting — the reroot transition g(child) = update(g(parent), …) is genuinely O(1) (subtract the child’s contribution, re-add the adjusted parent contribution). The pull pass visits each node once and the push pass visits each node once, so the total is Θ(n) outright.

  2. Non-invertible combine, O(deg) per node, still O(n) total. When the combine has no inverse (max, min, gcd, product modulo a prime, an associative monoid generally), you cannot “subtract” a child’s contribution. Instead you compute, at each node u of degree d, the prefix-and-suffix aggregates over its neighbor list (§3.1), which costs O(d) at that node. This is not O(1) per node — but it amortizes: the total work is Σ_u deg(u) = 2·(n − 1) by the handshake lemma (every edge contributes 1 to the degree of each of its two endpoints, and a tree has n − 1 edges). So Σ_u O(deg(u)) = O(n). The same Σ deg = 2(n−1) bound is exactly why the pull pass’s nested “for each child” loops are O(n) and not O(n·max_degree).

In other words, “rerooting is O(n)” is true, but the linearity in the non-invertible case rests on the handshake-lemma amortization rather than on an O(1)-per-node update. The auxiliary array USACO calls h[x] (“the value excluding the child that achieved the maximum”) and the prefix/suffix arrays of §3.1 are the concrete machinery that turns the per-node O(deg) work into the global O(n). The hidden assumption that can break linearity is the cost of a single combine: if combining two states is itself O(k) (e.g., merging size-k multisets), the totals scale by that factor — rerooting is O(n) in the number of combine operations, which equals node count only when each combine is O(1).

13. See Also

Graph View

Backlinks