Neural Mastery
← Practice
Aggregate Trace Spans Into a Treehard

Aggregate Trace Spans Into a Tree

hard Agents in Production 15 min

NumPy allowed · plain Python earns 10 bonus points

Implement span-tree reconstruction, assembling flat trace spans (each with a parent reference) into the real hierarchical call tree an observability UI actually displays.

Task

Implement build_span_tree(spans). Each span is {"id": str, "parent_id": str|None, "name": str}. Return a nested dict for the ROOT span (the one with parent_id is None): {"name": str, "children": [recursively nested child dicts]}, where children are sorted by id for determinism. Assume exactly one root exists.

Function Signature

build_span_tree(spans: list[dict]) -> dict

Examples

Example 1: root with one child
Input: spans = [{'id': 'a', 'parent_id': None, 'name': 'root'}, {'id': 'b', 'parent_id': 'a', 'name': 'child'}]
Output: {'name': 'root', 'children': [{'name': 'child', 'children': []}]}
Example 2: root with two children
Input: spans = [{'id': 'a', 'parent_id': None, 'name': 'root'}, {'id': 'b', 'parent_id': 'a', 'name': 'child1'}, {'id': 'c', 'parent_id': 'a', 'name': 'child2'}]
Output: {'name': 'root', 'children': [{'name': 'child1', 'children': []}, {'name': 'child2', 'children': []}]}
Example 3: root only no children
Input: spans = [{'id': 'a', 'parent_id': None, 'name': 'root'}]
Output: {'name': 'root', 'children': []}

Constraints

  • exactly one span has parent_id == None
Python3Saved ✓
def build_span_tree(spans):
# Your implementation here
pass

Case 1: root with one child
Input: spans = [{'id': 'a', 'parent_id': None, 'name': 'root'}, {'id': 'b', 'parent_id': 'a', 'name': 'child'}]
Expected: {'name': 'root', 'children': [{'name': 'child', 'children': []}]}
Case 2: root with two children
Input: spans = [{'id': 'a', 'parent_id': None, 'name': 'root'}, {'id': 'b', 'parent_id': 'a', 'name': 'child1'}, {'id': 'c', 'parent_id': 'a', 'name': 'child2'}]
Expected: {'name': 'root', 'children': [{'name': 'child1', 'children': []}, {'name': 'child2', 'children': []}]}
Case 3: root only no children
Input: spans = [{'id': 'a', 'parent_id': None, 'name': 'root'}]
Expected: {'name': 'root', 'children': []}