When replicating a decision tree between services, when must the serialization preserve its exact shape?

## The decision is about what the tree *means*, not how it encodes Two services need to agree on a tree that one of them holds in memory. There are two fundamentally different transfers available, and choosing between them is a judgment about the contract, not about bytes. **Shape-preserving transfer.** Encode the structure itself — a preorder stream with a marker for every empty child, or an equivalent unambiguous encoding — and rebuild it node for node. Roughly 2n+1 tokens for n nodes. The receiver ends up with the sender's tree. **Shape-free transfer.** Send the keys (with payloads) in canonical order and let the receiver construct its own structure. Roughly n tokens. The receiver ends up with *a* tree holding the same content. ### When shape is part of the contract Preserve it when any of these hold: - **Evaluation order is behaviour.** In a decision or routing tree the order predicates are tested determines which of several matching branches wins, and short-circuit effects change outcomes. Rebuilt shape means rebuilt behaviour. - **Node identity escapes the process.** If nodes carry identifiers that appear in audit trails, metrics, experiment assignments or explanations returned to a caller, two services must agree on which node is which, and a rebuild renumbers everything. - **Reproducibility is required.** If someone must replay a decision from six months ago and get the same path, the shape has to be pinned along with the keys. - **Per-node state exists beyond the key.** Thresholds, weights, counters, feature flags hanging off internal nodes — a rebuild has nowhere to put them. ### When shape is an implementation detail Ship keys only when the tree exists purely to answer lookups and ordered scans. Then a rebuild is not a loss; it is often an improvement: - **Half the wire.** No marker for each of the n+1 empty slots. - **Cheap and self-validating.** A sorted key stream is checked in one linear pass, and any receiver can build a balanced structure from it in O(n) without the O(n log n) of repeated insertion. - **Implementation independence.** The two sides may use different structures entirely, and either can change without renegotiating the format — a real benefit across a polyglot fleet. - **Degenerate shapes do not travel.** A source tree that has degraded into a chain replicates as a chain in the shape-preserving form, exporting a performance bug; the rebuild silently produces a good shape. That last point is the one that cuts both ways, and it is the crux of the whole judgment: **silently discarding shape is repair or data loss depending on whether shape was meaningful, and the wire format cannot tell the difference.** ### The organisational costs the format choice pins down - **Version skew.** A shape-preserving encoding is a promise about your internal node layout. The day a node gains a field, every decoder in the fleet must handle both layouts, and during a rolling deploy both versions are live simultaneously. Tag the encoding with a version, decide whether unknown fields are ignored or fatal, and know the deploy order that follows from that answer. The key-only form depends on far less, so it survives skew better. - **Maintenance.** A hand-rolled marker stream is compact, fast, and readable by exactly the code you wrote. A self-describing structured format is bulkier but debuggable by anyone with a text viewer and parseable by tooling you did not write. On a small team owning both endpoints the compact form is fine; across an organisation the debuggability usually wins, and the size difference rarely turns out to be the real constraint. - **Validation on receipt is not optional.** A structurally well-formed stream can still decode into a tree that violates an ordering invariant — corruption in transit, a sender bug, an older sender with different conventions about equal keys. Run the O(n) bounds or streaming-inorder validation after decoding and reject the payload loudly. Compared with the cost of serving wrong answers from a subtly broken replica, a linear pass is free. The key-only form gets this almost for nothing, since checking that the incoming keys are ordered *is* the validation. - **Migrating without pausing writes.** If the source keeps changing during the transfer, neither format is enough on its own — you need a snapshot boundary plus a change stream applied afterwards. The shape-free form is easier here, because incremental key updates compose, while structural deltas depend on a shape both sides must already agree on. ### How to answer this in an interview State the deciding question first — is shape semantic? — then commit to a default and name what would change your mind. A reasonable default: ship keys and rebuild, because most trees are indexes; switch to shape-preserving encoding the moment node identity or evaluation order leaves the process, and in that case pay for a version tag and receipt-side validation as part of the deal.