# Maintain an Out-of-Order Step Progress Tree Each progress event contains: ```text timestamp: integer step_id: integer parent_step_id: integer or null run_state: string text: string ``` Implement `StepTracker.add_event(event)` and `StepTracker.snapshot()`. Events may arrive out of timestamp order, and a step may receive many updates. Keep only the event with the greatest timestamp for each `step_id`; on equal timestamps, the later arrival wins. A child may arrive before its parent. The latest event also defines the step's current parent, so a newer update may reparent a node. `snapshot()` returns a forest of nested nodes containing `step_id`, `run_state`, `text`, and `children`. Roots have a null or currently unknown parent. Sort roots and each child list by `step_id`. Reject an update that would make a step its own ancestor; leave the previous state unchanged. ## Constraints - Up to `200000` events and distinct steps. - Parent links in every accepted snapshot form a forest. - `add_event` should be efficient for incremental updates; `snapshot` may take `O(N)`. - Avoid recursive output traversal that can overflow on a deep tree. ## Example If child step `2` with parent `1` arrives before step `1`, the first snapshot shows `2` as a temporary root. After step `1` arrives, the next snapshot nests `2` under `1`. An older update for step `2` is ignored. ## Clarifications Describe the indexes used for direct node lookup, pending or unknown parents, reparenting, and cycle detection. State the cost of an update and a full snapshot. ## Hints Use a node map for identity and explicit parent/child bookkeeping; build the returned projection iteratively from current roots. ## Extensions - Preserve a stable display order other than numeric step ID. - Emit only the subtree changed by an event. - Make updates thread-safe without rebuilding the forest.