Capstone 2 · Week 108 · Optional Boss Fight

Multi-Tenant Agent Execution Forensics

Euler Tour + DSU on Tree. This extends Capstone 1 from a flat event log to a forest of agent execution trees. You will combine systems design with tree algorithms and exact subtree queries.

You will fail if you treat a tree like an array

Subtree structure is data, and Euler order is the indexing strategy that makes it queryable.

The scenario

Your LLM gateway now serves ReAct / Plan-Execute agents. Each request spawns an execution tree; thousands of tenants, 10k agent traces/sec, each tree 10–50k nodes worst case, nodes arrive out-of-order, duplicates from retries. Engineers need exact subtree forensics: which tool failed the most under this node? How many distinct tools errored? How many tokens wasted?

trace_id: tr_9f8s7d
root (agent planner) [model=claude-4, tokens=1200]
 ├── tool: search_docs [tool_id=12, status=ok, tokens=400]
 │    ├── tool: embed_query [tool_id=5, error, tokens=200]
 │    └── tool: rerank [tool_id=12, error, tokens=150]
 └── tool: code_exec [tool_id=8, error, tokens=800]
      └── tool: search_docs [tool_id=12, ok, tokens=100]

Why Euler + DSU, not a recursive CTE

Recursive CTE over 50k-node trees × 200k queries = death. Flatten once via an Euler Tour so every subtree is a contiguous range [tin, tout], then answer queries over an array. For a batch of offline subtree queries on the same tree, DSU on Tree (sack / keep-heavy) gives O(N log N + Q).

The coding problem

Rooted tree of agent nodes, each with tool_id, is_error, tokens. Q offline queries; for each node u return: top_error_tool (max error count, ties → smallest tool_id), top_error_count, distinct_error_tools, wasted_tokens.

    0(tool=1, err=T, 100)
   / \
  1(2,F,50) 2(1,T,200)
            / \
        3(3,T,10) 4(2,T,70)

Queries: [0, 2]
Subtree 0: tool1:2, tool2:1, tool3:1 -> top=1 count=2 distinct=3 wasted=380
Subtree 2: tool1:1, tool2:1, tool3:1 -> tie, smallest id -> top=1 count=1 distinct=3 wasted=280

The DSU invariant

Right before answering queries at u, the active sack contains exactly all nodes in subtree(u), and no nodes outside it. Prove it:

Every light child is processed and cleared.
The heavy child remains.
Every light subtree is added exactly once.
u is added.
Therefore the sack equals subtree(u).
If keep=false, all of subtree(u) is removed before returning.

Pitfalls index

tout = timer-1 vs tin+size-1 confusion → off-by-one, queries miss nodes

Forgetting to compress tool_id and tie-break on the original

Adding non-error nodes to the aggregates

Not walking max_freq down on remove → stale top

Python recursion limit - use iterative or setrecursionlimit

Adding the heavy child twice (dfs + add_subtree loop)

min() over a plain set bucket is O(K) - mention SortedSet/heap in production

Not handling the keep flag - leaks light subtree data into siblings

Forgetting heavy child → O(N²) instead of O(N log N)

#10

No cycle detection → stack overflow in the Euler pass

Follow-ups that change the machinery

If the query becomes…	Use
Path (u → v), not subtree	Heavy-Light Decomposition; offline exact path mode → Mo's on Tree
Tree mutates (reparenting)	Euler Tour Tree or Link-Cut Tree
Top-K error tools per subtree	Counter + heap of (count, tool); Space-Saving as approximate alternative
One huge tree split across shards	Full frequency map needed - top-1 is not mergeable

The progression it teaches

Flat log → range query → Mo's. Execution tree → subtree → Euler interval → DSU on Tree. Path query → different workload → different machinery. Mutable tree → static preprocessing invalid → dynamic structures. Do not select an algorithm because the query sounds similar - select it from topology, mutability, workload shape, and aggregation algebra.