When does a preprocessed lowest-common-ancestor index beat a per-query walk on a large, changing tree?
answer
- measure the real depth first
- queries per second versus mutations per second
- the index is a cache of tree shape
- appends are cheap, re-parenting is not
- a stale index is wrong, not slow
basics
~20 sWhen queries are frequent, the tree is deep, and mutations are rare or append-only. An index buys O(log n) queries for O(n log n) build time and memory, and re-parenting invalidates it. On a shallow or churning tree the walk wins.
solid answer
~50 sMeasure before you build. A per-query walk costs `O(h)` with parent pointers, so on a category tree six levels deep it is six pointer hops — no index improves a number that was never the bottleneck. Preprocessing earns its keep when `h` is large, query volume is high, and the shape is stable: binary lifting builds in `O(n log n)` time and memory for `O(log n)` queries; an Euler-tour plus range-minimum structure reaches `O(1)` queries at similar build cost. The decisive axis is usually mutation. An append-only tree is friendly — a new leaf's ancestor table derives in `O(log n)` from a parent whose table never changes — while moving a subtree shifts every depth beneath it and invalidates that region. Weigh ownership too: a stale index returns a wrong ancestor silently, unlike one that is merely slow.
go deeper
Know that ancestor queries can be answered either by walking each time or by precomputing, and that precomputing costs memory and build time up front. The choice is not yours to make yet, but the tradeoff should not surprise you.
Be able to state the build, query and memory costs of the main options and explain why a stable tree is what makes precomputation pay off at all.
Show the measurement first — observed depth and query rate — and reason about what a structural update does to a precomputed index. Say how you would detect staleness in production.
Own the whole call: whether to build, what constraint on the data model would make maintenance sound, what it costs across the fleet, who maintains it, and how a wrong answer would be noticed. Be as willing to defend not building it as building it.
## The decision, not the algorithm Everybody can recite that a preprocessed ancestor index answers queries faster than a walk. The principal-level question is whether to build one at all, and that is decided by four numbers and one organisational fact: the tree's real height, the query rate, the mutation rate and shape, and the memory ceiling — plus who maintains the thing after you rotate off. ## The options, honestly costed | Approach | Build | Query | Memory | Survives updates? | | --- | --- | --- | --- | --- | | Walk up with parent pointers | none | `O(h)` | `O(1)` | trivially | | Downward recursion, no parent links | none | `O(n)` | `O(h)` stack | trivially | | Binary lifting (`2^k`-th ancestor tables) | `O(n log n)` | `O(log n)` | `O(n log n)` | append-only: yes, incrementally | | Euler tour + range-minimum structure | `O(n log n)` | `O(1)` | `O(n log n)` | no: a structural change rewrites the tour | | Offline batch with union-find | `O((n + q) * alpha)` | amortized near-constant | `O(n)` | n/a — one batch, one shape | Two notes on the table. First, an `O(n)`-build variant of the constant-query approach exists, but it is intricate enough that its real cost is comprehension, not cycles. Second, the union-find batch method requires all queries up front; it is the right answer surprisingly often, because plenty of ancestor workloads are a nightly job over a known query set rather than an online endpoint. ## Start by measuring h The most common mistake is optimizing a term that is already small. A product-category tree is typically single-digit depth by design, because merchandisers cannot navigate more. `O(h)` there is a handful of pointer hops — nanoseconds inside a request that spends milliseconds elsewhere. Building an index for it adds a second structure to keep correct on every write path and buys nothing measurable. Contrast a deep revision history where the chain from a recent state to a shared base can be tens of thousands of steps: there the walk is genuinely the cost, and it is worth paying to remove it. So the first artifact of this decision is not a design doc, it is a histogram of observed depths and a count of queries per second. If either number is unremarkable, the decision is "do not build", and saying so confidently is the senior move that a whole team's roadmap benefits from. ## Mutation is the axis that decides it An index is a cached derivation of the tree's shape, so every shape change is a cache-invalidation event, and different indexes fail differently: - **Appending leaves** is benign for binary lifting. A new node's table of `2^k`-th ancestors is computed from its parent's table in `O(log n)`, and no existing entry changes, because appending never alters an existing node's depth or ancestry. An append-only history is close to the ideal workload. - **Re-parenting a subtree** is the hard case. Every depth beneath the moved node changes, so every ancestor table in that region is stale. Nothing crashes: queries stay fast and return wrong ancestors. That asymmetry — a wrong answer, not a slow one — is exactly why this decision belongs to whoever owns correctness, not just latency. - **An Euler-tour structure** is worse still, since the tour is a global linearization; a structural edit generally forces a rebuild. If the tree churns structurally, the realistic options are: rebuild on a schedule and accept a staleness window (only sound if queries tolerate it), maintain the index transactionally with the write (a real burden on every write path), or do not build it. ## The costs that do not appear in the complexity table **Memory across a fleet.** `O(n log n)` for a tree of tens of millions of nodes is a serious number, multiplied by every replica holding a copy. Compare it against the memory ceiling per instance before, not after. **Maintainability.** A parent-pointer walk is five lines that any reviewer can verify. An ancestor-table build with an off-by-one in the level loop passes most tests and is wrong on a narrow class of inputs. Ask whether the team can own it in a year, and whether the failure would be noticed. **Verification.** If you do build it, keep the naive walk in the codebase and assert the index against it on a sampled fraction of queries or in a shadow job. It is cheap, it is the only thing that catches a silent staleness bug, and it makes the index safe to keep rather than a thing people fear touching. ## How to defend the decision The strongest version of the argument is a rejection with numbers: "observed depth p99 is nine, query volume is 400 per second, the walk costs under a microsecond and the endpoint budget is 40 milliseconds; an index would add `O(n log n)` memory per replica and a new invariant on four write paths, for no measurable gain." The second-strongest is a conditional yes: build it, restrict the tree to append-only at the model level so incremental maintenance is sound, and keep the naive path as the oracle. Both beat picking the asymptotically better structure on principle — which is the failure mode this question exists to expose.
- How would you argue against building the index to a team that wants the fastest possible query?With the measured depth and the latency budget side by side. If the tree is nine levels deep, the walk is nine pointer hops inside a request that spends milliseconds elsewhere, so the index optimizes a term nobody can observe. Its real price is a second structure that every write path must keep correct — a permanent tax for an unmeasurable gain.
- What makes an append-only tree especially friendly to a preprocessed ancestor index?Appends only add leaves, so no existing node's depth or ancestry changes. A new node's `2^k`-th-ancestor table derives in `O(log n)` from its parent's table, which is already final. Incremental maintenance is therefore local and provably sound — the property that collapses the moment arbitrary re-parenting is allowed.
- If you do build an index, how do you keep it honest in production?Keep the naive walk as an oracle and compare against it on a sampled fraction of queries or in an offline shadow job. A stale index returns a plausible wrong ancestor with no error and no latency signal, so nothing else will tell you. Alerting on a mismatch rate is the difference between a maintainable index and a feared one.
- When is answering the whole query set offline the better choice?When queries arrive as a known batch rather than one at a time — a nightly rollup, a bulk import reconciliation. A union-find-based batch pass answers all of them in near-linear total time with far less machinery than an online index, and it holds no state between runs, so there is nothing to invalidate.
saying these in an interview costs you the question
- Builds an index before measuring the tree's actual depth
- Treats O(1) queries as free of memory and build cost
- Forgets that structural updates leave the index silently wrong
- Assumes a hand-rolled index is maintenance-free
- Ignores that a known batch of queries can be answered offline