Traverse org chart level by level

Q: Traverse org chart level by level

This question evaluates understanding of hierarchical data modeling and tree traversal, specifically breadth-first (level-order) traversal and reconstruction of a tree from manager–employee relationships.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem

You are given an organization chart as manager relationships.

Each employee is represented by:

employee_id (string/int)
manager_id (string/int or null ), where null indicates the CEO/root

Assume the org chart forms a valid tree (exactly one root, no cycles), but employees may appear in any order.

Task

Return the employees top-down, level by level (i.e., breadth-first order).

Input

A list of pairs/records:

(employee_id, manager_id)

Output

One of the following (choose one and state which you implement):

A list of lists, where each inner list contains employee_ids at the same depth, ordered left-to-right by insertion order (or sorted if you prefer), e.g. [[CEO], [A,B], [C,D,E]] ; or
A single list of employee_ids in BFS order.

Example

Input:

("CEO", null)
("A", "CEO")
("B", "CEO")
("C", "A")

Output (option 1):

[["CEO"], ["A","B"], ["C"]]

Constraints / Edge cases

Employees may be given before their manager appears in the input.
Large orgs: aim for O(n) time and O(n) memory.