Answer ancestor-walk queries on a rooted tree

Q: Answer ancestor-walk queries on a rooted tree

This question evaluates understanding of tree data structures and ancestor-walk queries, assessing competency in traversing rooted trees, interpreting parent arrays, and designing efficient query-processing methods for large n and q.

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

Problem (Tree / Parent Array Queries)

You are given a rooted tree with n nodes labeled 1..n, represented by a parent array par[1..n]:

par[i] is the parent of node i
par[root] = -1
The input guarantees this forms a valid rooted tree (exactly one root, no cycles).

Example:

par = [-1, 1, 1, 2, 2, 2, 2] (meaning par[1] = -1 , par[2] = 1 , …)

You will be given q queries. Each query provides:

a starting node u
an integer k ≥ 0 (“number of commands/steps”)

For each query, start at node u and move to the parent exactly k times (or until you reach the root). If you reach the root before using all steps, you remain at the root.

Output

For each query, output the label of the final node where you stop.

Constraints (assume large input)

Design an approach efficient for large n, q (e.g., up to 2e5).

Answer ancestor-walk queries on a rooted tree

Overview

Problem (Tree / Parent Array Queries)

Output

Constraints (assume large input)

Comments (0)