Find k-th recipient in command propagation order

Q: Find k-th recipient in command propagation order

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.

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.

Q: What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Imc.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Imc during technical interviews.

Question

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:

Consider u ’s direct children, sorted by increasing person id.
Send the command to the smallest-id child first.
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).