Trace Tree & Critical Path (Rust)
Topics: graphs, DFS, observability, trace analysis
Problem
A distributed trace is a tree of spans: each span has an ID, the ID of its parent span (empty
for the root), and its own duration. A span's children run concurrently, so a span only finishes
once its slowest descendant chain finishes. The critical path is the root-to-leaf chain of spans
that determines the trace's total latency — the chain you'd optimize to make the request faster.
pub struct Span { pub id: String, pub parent: String, pub name: String, pub duration: i64 }
pub enum TraceError { NoRoot, MultipleRoots, UnknownParent, Cycle }
pub struct CriticalPath { pub spans: Vec<String>, pub total: i64 }
pub fn critical(spans: &[Span]) -> Result<CriticalPath, TraceError>;
For a span s:
finish(s) = s.duration + max over children c of finish(c) (0 if s is a leaf)
critical returns the chain of span IDs from the root down to the leaf that realizes that maximum,
and total is its summed duration.
- Children run concurrently — pick the child with the largest finishing time at each step.
- Deterministic ties: when two children finish at the same time, choose the one with the
lexicographically smaller ID.
- The spans must form exactly one tree. Return:
NoRoot — no span has an empty parent,MultipleRoots — more than one does,UnknownParent — a span's parent ID isn't present,Cycle — parent links form a loop (some spans never reach the root).
root(10) → a(5) → c(20) → {[root a c], 35}
root(10); a(5)→c(20); b(30) (a,b under root) → {[root b], 40} // 30 > 5+20
root(0); a(10), b(10) under root → {[root a], 10} // tie → smaller ID
A depth-first walk that returns each subtree's heaviest path makes both the max-pick and the
tie-break fall out naturally; validate the tree (one root, known parents, no cycle) before walking.
Grading
Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using
rustc --test. Only solution.rs is yours to edit.
Sign in to submit your solution.