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** ```json [ {"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)** ```json [ { "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).