Build span trees from unordered trace spans

You are given an unordered list of span objects. Each span is a map/dictionary containing at least:

• span_id (string, unique)
• parent_id (string or null )
• start_time (integer timestamp)

A span is considered a root span if:

1. parent_id is null , or
2. parent_id is non-null but does not match any existing span_id in the input (i.e., its parent is missing). Such a span is an orphan and must be treated as a root.

Build the output as a list of root spans, where each span is augmented with a children field (a list of its direct child spans). The children list for every span must be sorted by increasing start_time (if two children have the same start_time, you may keep input order or break ties by span_id, but be consistent).

Return the list of root spans (i.e., the forest of span trees). The order of the root spans themselves is not strictly specified unless you choose to sort them similarly (state your choice).

Example

Input

[
  {"span_id":"span_1", "parent_id":null,     "start_time":300},
  {"span_id":"span_2", "parent_id":"span_1","start_time":500},
  {"span_id":"span_3", "parent_id":"span_1","start_time":300},
  {"span_id":"span_4", "parent_id":"span_2","start_time":500},
  {"span_id":"span_5", "parent_id":"span_6","start_time":600},
  {"span_id":"span_7", "parent_id":null,     "start_time":1000}
]

Output (one valid formatting)

[
  {
    "span_id":"span_1",
    "parent_id":null,
    "start_time":300,
    "children":[
      {"span_id":"span_3","parent_id":"span_1","start_time":300},
      {
        "span_id":"span_2",
        "parent_id":"span_1",
        "start_time":500,
        "children":[
          {"span_id":"span_4","parent_id":"span_2","start_time":500}
        ]
      }
    ]
  },
  {"span_id":"span_5","parent_id":"span_6","start_time":600},
  {"span_id":"span_7","parent_id":null,"start_time":1000}
]

Notes / Assumptions to clarify in your solution

• Every span_id is unique.
• There may be multiple roots.
• A span whose parent_id is missing becomes a root (an orphan).
• (Optional) Decide how to handle cycles if they appear (not expected in valid traces).