Trace Tree & Critical Path (C)
Topics: graphs, trees, DFS, longest path
Problem
Given the spans of a distributed trace (each pointing at its parent), reconstruct
the tree and find the critical path — the chain of spans from the root to a
leaf that determines the trace's total latency.
typedef enum { TRACE_OK, TRACE_NO_ROOT, TRACE_MULTIPLE_ROOTS, TRACE_UNKNOWN_PARENT, TRACE_CYCLE } TraceStatus;
typedef struct { const char *id; const char *parent; const char *name; int duration; } Span;
TraceStatus critical(const Span *spans, int n, const char **out_path, int *out_len, int *out_total);
A span is the root iff its parent is empty ("" or NULL). On TRACE_OK, write
the path (span IDs, root first) into out_path[0..*out_len) and the total latency
into *out_total.
Validation (the spans must form one valid tree):
TRACE_NO_ROOT / TRACE_MULTIPLE_ROOTS — there must be exactly one root.TRACE_UNKNOWN_PARENT — a non-root span names a parent that isn't present.TRACE_CYCLE — parent links form a cycle (some span can't reach the root).
Key concepts
- Critical path = longest path by duration: a node's critical path is the node
followed by the critical path of its heaviest child (the one whose subtree
total is largest). A node's own
duration always adds; siblings run in parallel,
so only the slowest chain counts.
- Deterministic ties: visit children in ID order and compare strictly, so
equal totals keep the smaller ID.
- Cycle detection by reachability: since every non-root span has a present
parent, the only way a span is unreachable from the root is a parent cycle —
count nodes reached from the root and compare to the total.
A children-by-scan helper plus fixed-size path/stack buffers suffice — no
allocation.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/trace && /tmp/trace
Sign in to submit your solution.