Answer Kth-Ancestor Queries with the Native Tree Class
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
The parent array describes a tree on 0..n-1 rooted at 0. Implement TreeAncestor(n,parent),then getKthAncestor(node,k) to return the ancestor reached by moving k parent edges upward,or -1 if that many ancestors do not exist.
```cpp
class TreeAncestor {
public:
TreeAncestor(int n, vector<int>& parent);
int getKthAncestor(int node, int k);
};
```
### Examples
**Example 1:**
```text
Calls: TreeAncestor(4,[-1,0,1,1]); getKthAncestor(3,1); getKthAncestor(3,2); getKthAncestor(3,3)
Returned query values: [1,0,-1]
Explanation: The ancestor chain of3 is1,then0,and then absent.
```
**Example 2:**
```text
Calls: TreeAncestor(1,[-1]); getKthAncestor(0,1)
Returned query values: [-1]
Explanation: The root has no parent.
```
### Constraints
- `1 <= k <= n <= 50000`; parent.length equals n.
- parent[0] is -1; for every other node,`0 <= parent[i] < n`.
- parent describes a tree rooted at 0,and `0 <= node < n`.
- At most 50000 queries are made.
### Contract considerations
Preserve the native constructor and getKthAncestor query protocol; do not replace it with a different public API.
```hint Read the boundary condition
Check root queries and requests beyond a node's ancestor chain. Preserve the constructor and successive-query behavior.
```
### Boundary reminders
Preserve the native constructor and getKthAncestor query protocol; do not replace it with a different public API.
Overview: Answer Kth-Ancestor Queries with the Native Tree Class. The parent array describes a tree on0..n-1 rooted at0.