Trace Tree & Critical Path (Go)
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.
type Span struct { ID, Parent, Name string; Duration int }
type CriticalPath struct { Spans []string; Total int }
func Critical(spans []Span) (CriticalPath, error)
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:
ErrNoRoot — no span has an empty parent,ErrMultipleRoots — more than one does,ErrUnknownParent — a span's parent ID isn't present,ErrCycle — 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.
Run
go test -v ./challenges/trace-critical-path/go/
Sign in to submit your solution.