Build a Trace Forest
Problem statement
Build a trace forest from an unordered list of spans. Parallel arrays give each span's ID, original parent ID and start timestamp. An empty parent ID means no parent. If a nonempty parent ID does not occur among the span IDs, the span is an orphan and also becomes a root. Otherwise attach it as a child of that parent, even when the parent appears later in the input.
Keep roots in their original input order. Within each parent, sort its direct children by increasing start timestamp; break equal-time ties by original input order. Do not globally sort unrelated spans.
Output adapter: represent the resulting nested forest by preorder rows [spanId, originalParentId, startTime, depth], with all four entries strings. Start each root at depth zero, output a node before its children, and finish its whole subtree before the next root. Write numeric entries in ordinary decimal notation. Preserve the original parent ID in every row, including an orphan's missing parent name. These rows encode the full hierarchy and child ordering for the three reported metadata fields. An empty input returns an empty array.
Function
buildTraceForest(spanIds: String[], parentIds: String[], startTimes: long[]) → String[][]Examples
Example 1
spanIds = ["span_1","span_2","span_3","span_4","span_5","span_7"]parentIds = ["","span_1","span_1","span_2","span_6",""]startTimes = [300,500,300,500,600,1000]return = [["span_1","","300","0"],["span_3","span_1","300","1"],["span_2","span_1","500","1"],["span_4","span_2","500","2"],["span_5","span_6","600","0"],["span_7","","1000","0"]]The roots are span_1, orphan span_5, and span_7, in their input order. The children of span_1 are span_3 at time 300 followed by span_2 at 500. Span span_4 is below span_2 at depth two. The orphan keeps its original missing parent name span_6.
Example 2
spanIds = ["c","b","a"]parentIds = ["a","","b"]startTimes = [5,7,3]return = [["b","","7","0"],["a","b","3","1"],["c","a","5","2"]]Span b is the only root. Although c appears before its parent a, it attaches below a, which attaches below b. Preorder is b,a,c, with depths 0,1,2. Parent timestamps do not control ancestry.
Example 3
spanIds = []parentIds = []startTimes = []return = []There are no spans, so the forest and its preorder encoding are empty.
Constraints
0 <= spanIds.length <= 100spanIds.length == parentIds.lengthandspanIds.length == startTimes.length.- Every span ID has between
1and32characters. Span IDs are unique. - Every parent ID has between
0and32characters; the empty string means no parent. - Nonempty IDs contain only ASCII letters, digits, underscores and hyphens.
0 <= startTimes[i] <= 1000000000- Following links to existing parents never forms a cycle.