Maintain an Out-of-Order Step Progress Tree

Problem Statement

You are building a real-time progress tracker for complex workflows. You receive a stream of StepUpdate events, where each event updates the state of a step or defines its parent relationship. Steps can be created in any order, and parent references may refer to steps that have not been seen yet.

An event is defined as: {step_id: str, status: str, parent_id: str | None, timestamp: int}.

Requirements

1. Hierarchy: If a step is assigned a parent_id, it becomes a child of that step. If a step is reassigned to a new parent, it moves in the tree.
2. Out-of-order: Updates for a child might arrive before the parent exists, or later updates might arrive with older timestamps. Always honor the state of the update with the highest timestamp for a specific step_id.
3. Cycle Prevention: If a parent_id assignment creates a cycle, ignore that specific assignment (keep the previous valid parent) and log an error.
4. Snapshot: Implement a method get_tree() that returns a nested dictionary representation of the current valid forest, where keys are step_id and values are their respective children.

Function Signature

class ProgressTracker:
    def update(self, event: dict) -> None:
        # Update internal state with new event

    def get_tree(self) -> dict:
        # Returns the current forest representation

Constraints

• step_id is unique.
• A step can have at most one parent.
• Updates are processed sequentially by the system, but the timestamp field determines which update is considered the "latest" state for a given step_id.
• You must handle orphan nodes (steps whose parent does not exist yet) by keeping them in the forest until their parent arrives.

Example

# Update 1: {step_id: "B", parent_id: "A", timestamp: 10}
# Update 2: {step_id: "A", parent_id: None, timestamp: 5}
# Result of get_tree(): {"A": ["B"]}

Edge Cases

• A step claiming to be its own parent (direct cycle).
• A parent ID that never appears in the event stream.