Find k-th recipient in command propagation order
Company: Imc
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## Chain of Command (k-th Receiver in DFS-by-Child-Id Order)
A company org chart forms a rooted tree with `n` people (nodes), labeled `1..n`.
You are given an array `parent[1..n]` describing the tree:
- `parent[i] = -1` means `i` is the root (top leader)
- otherwise, `parent[i]` is the direct manager (parent) of person `i`
- each node has zero or more direct reports (children)
### Command propagation rule
When a person `u` issues a command, it is sent to **all subordinates** of `u` (all descendants of `u`), using this strict order:
1. Consider `u`’s direct children, sorted by increasing person id.
2. Send the command to the smallest-id child first.
3. Before sending to the next child, the command must be **fully propagated** throughout the current child’s entire subtree using the **same rule**.
This defines a deterministic traversal order over the descendants of `u`:
- It is equivalent to a DFS preorder over `u`’s subtree **excluding `u`**, where children are visited in ascending id.
### Task
Given:
- `parent[1..n]`
- an issuer `u`
- an integer `k` (1-indexed)
Return the person id of the **k-th** subordinate who receives the command in the propagation order.
If `u` has fewer than `k` descendants, return `-1`.
### Input/Output
- Input: `parent[]`, `u`, `k`
- Output: the person id of the k-th recipient, or `-1`
### Notes / Assumptions
- The input forms a valid tree (exactly one root).
- `k` is 1-indexed over recipients (descendants only; the issuer `u` is not counted).
- Constraints may be large (e.g., `n` up to 2e5), so an approach better than simulating propagation step-by-step for each query is typically expected (if multiple queries are present, state how many).
Quick Answer: This question evaluates understanding of tree traversals, subtree indexing, and order-statistics on rooted trees, focusing on DFS-preorder propagation when children are visited in ascending id.
A company org chart forms a rooted tree with `n` people labeled `1..n`. You are given `parent`, a 0-indexed array of length `n` where `parent[i]` is the manager id of person `i+1`; a value of `-1` marks the root (top leader). Every non-root person has exactly one manager and zero or more direct reports.
When a person `u` issues a command it is propagated to all of `u`'s descendants in a strict order: at each node, visit the direct children in increasing id order, and before moving on to the next child, fully propagate the command through the current child's entire subtree using the same rule. This is exactly a DFS preorder over `u`'s subtree, excluding `u`, with children visited in ascending id order.
Given `parent`, an issuer `u`, and a 1-indexed integer `k`, return the person id of the k-th subordinate to receive the command. If `u` has fewer than `k` descendants, return `-1`.
Constraints
- 1 <= n <= 2 * 10^5 (n = len(parent))
- People are labeled 1..n; parent is 0-indexed so parent[i] describes person i+1.
- Exactly one entry of parent equals -1 (the unique root).
- 1 <= u <= n
- 1 <= k, and the input forms a valid tree (no cycles).
- If u has fewer than k descendants, return -1.
Examples
Input: ([-1, 1, 1, 2, 2, 3], 1, 3)
Expected Output: 5
Explanation: children[1]=[2,3], children[2]=[4,5], children[3]=[6]. DFS preorder from root 1 (excluding 1): 2,4,5,3,6. The 3rd recipient is 5.
Input: ([-1, 1, 1, 2, 2, 3], 1, 1)
Expected Output: 2
Explanation: The first recipient is the smallest-id child of the root, which is 2.
Hints
- Build a children adjacency list from parent, then sort each node's children by id so the smallest-id child is visited first.
- The propagation order is exactly a DFS preorder of u's subtree with u itself excluded — count nodes as you pop them and stop when the count reaches k.
- Use an explicit stack and push children in reverse id order so the smallest id is processed next; this avoids recursion-depth limits for chains up to 2*10^5 deep.