Traverse an Org Chart by Level

You are given an organization's reporting structure as a flat list of employee-manager relationships. Exactly one employee is the root (the CEO) and has no manager.

Example input schema:

• employee_id: int
• employee_name: string
• manager_id: int | null

Task:

1. Convert the flat reporting structure into a tree.
2. Return the org chart from top to bottom, one level at a time.
3. Each level should be shown in full before moving to the next level.

Example output format:

• [[CEO], [VP1, VP2], [Mgr1, Mgr2, Mgr3], ...]

Discuss:

• your data structures,
• time and space complexity,
• and how you would handle invalid input such as cycles, missing managers, or multiple roots.

Traverse an Org Chart by Level

You are given an organization's reporting structure as a flat list of employee records. Each record has the form [employee_id, employee_name, manager_id], where manager_id is None for the CEO. Convert the flat reporting structure into an org chart tree and return the employee names from top to bottom, one level at a time. Each level must be completed before moving to the next level. Children under the same manager should appear in the same relative order as they appear in the input list. If the input is invalid, return an empty list. Invalid input includes: no employees, duplicate employee IDs, multiple roots, no root, a missing manager reference, or a cycle/disconnected component.

Constraints

• 0 <= len(employees) <= 100000
• employee_id values must be unique for valid input
• Exactly one employee must have manager_id == None for valid input
• Every non-root manager_id must refer to an existing employee_id
• The reporting structure must form one connected acyclic tree
• Employee names may repeat

Hints

1. Build a mapping from manager_id to the list of direct reports. This gives you the tree edges.
2. After finding the root, use BFS with a queue to collect employees level by level. Track visited IDs to detect cycles or unreachable employees.