Render an Organization Chart and Find Skip-Level Pairs

Build an organization tree from manager/direct-report rows. Support rendering the tree with indentation and listing all skip-level pairs, where the second employee is exactly two edges below the first.

Implement org_chart(relations: string[][], mode: int) -> string[]:

• A row [manager, child1, child2, ...] lists that manager's direct reports in display order.
• mode == 0: return the rendered lines in preorder. Prefix each employee with four dots per depth level; the root has no prefix.
• mode == 1: return skip-level pairs encoded as manager,employee, with one comma and no spaces. Visit managers in tree preorder; for each manager, visit its children and then each child's children in the stored order.

Constraints & Assumptions

• Each employee name is a nonempty ASCII string of letters, digits, or underscores.
• Each manager appears as the first item of at most one row, and no direct-report list contains a duplicate.
• The rows describe one valid rooted tree with at most 2,000 employees: no cycles, one parent per non-root employee, and exactly one root. The root is not separately supplied.
• A one-element row can represent an employee with no reports. An empty relation list represents an empty chart and returns an empty list in either mode.
• Employees that appear only as children are leaves. Preserve input child order; do not alphabetize it.
• The mode interface and pair serialization are explicit practice encodings of the reported class methods. Skip-level means exactly two levels, not all descendants beyond one level.

Examples

relations = [["A","B","C"],["B","E"],["C","D"]]
mode = 0
result = ["A","....B","........E","....C","........D"]

relations = [["A","B","C"],["B","E"],["C","D"]]
mode = 1
result = ["A,E","A,D"]

Explain the time and space costs of building the tree, rendering it, and listing skip-level pairs, including the size of the returned strings. Describe tests for a single root, a chain, and a branching tree.

Hint: Separate depth from skip-level distance

Rendering uses each node's depth from the root. A skip-level pair uses only a manager's children and their children, regardless of that manager's absolute depth.

Render an Organization Tree and List Skip-Level Pairs

Approach

Build a manager-to-ordered-children map and collect all names and all reported children. In a nonempty valid tree, the unique name absent from the child set is the root. Child-only names need no explicit row and have no reports. Use an iterative preorder stack, pushing direct reports in reverse order so popping preserves their stored order. Rendering appends four dots per stored depth. Pair mode emits a manager's children's children in their nested stored order before visiting later managers; these are exactly its distance-two descendants. It does not emit direct reports or more distant descendants. Building and walking require O(n) expected map/set work plus name characters for n employees. Rendering additionally costs the total emitted character count L, which can be quadratic in n on a chain because indentation grows with depth. Every nonroot employee at depth at least two has one grandparent, so pair mode emits at most n-2 pairs and costs O(n+L). State is O(n) entries plus stored names and output; explicit traversal avoids deep recursion.

• Time complexity: O(n + input name characters + output characters) expected
• Space complexity: O(n) entries plus names and returned strings