# Kth Ancestor of a Tree Node
**Difficulty:** HARD
[External](https://leetcode.com/problems/kth-ancestor-of-a-tree-node)
Canonical: https://scaleengineer.com/dsa/problems/kth-ancestor-of-a-tree-node
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree
---
## Problem
You are given a tree with `n` nodes numbered from `0` to `n - 1` in the form of a parent array `parent` where `parent[i]` is the parent of `ith` node. The root of the tree is node `0`. Find the `kth` ancestor of a given node.

The `kth` ancestor of a tree node is the `kth` node in the path from that node to the root node.

Implement the `TreeAncestor` class:

* `TreeAncestor(int n, int[] parent)` Initializes the object with the number of nodes in the tree and the parent array.
* `int getKthAncestor(int node, int k)` return the `kth` ancestor of the given node `node`. If there is no such ancestor, return `-1`.

**Example 1:**

![](https://assets.glich.co/dsa/kth-ancestor-of-a-tree-node/image0.png) 

**Input**
["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]]
**Output**
[null, 1, 0, -1]

**Explanation**
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);
treeAncestor.getKthAncestor(3, 1); // returns 1 which is the parent of 3
treeAncestor.getKthAncestor(5, 2); // returns 0 which is the grandparent of 5
treeAncestor.getKthAncestor(6, 3); // returns -1 because there is no such ancestor

**Constraints:**

* `1 <= k <= n <= 5 * 104`
* `parent.length == n`
* `parent[0] == -1`
* `0 <= parent[i] < n` for all `0 < i < n`
* `0 <= node < n`
* There will be at most `5 * 104` queries.

# Approaches
## Simple Iteration (Brute Force)
This approach involves directly simulating the process of finding an ancestor. To find the k-th ancestor of a node, we simply traverse upwards from the given node towards the root, one step at a time, for `k` steps.
**Time:** Constructor: `O(n)` to copy the parent array. `getKthAncestor`: `O(k)` for each query, which is `O(n)` in the worst case. Total for `Q` queries: `O(n + Q * n)`. This is too slow given the constraints and will result in Time Limit Exceeded. · **Space:** `O(n)` to store the parent array.
**Pros:** Very simple to understand and implement.; Low memory usage.; Fast constructor.
**Cons:** Inefficient for queries with large `k`.; Fails to pass time limits on platforms like LeetCode for the given constraints.
### Explanation
### Constructor `TreeAncestor(n, parent)`
The constructor's role is minimal. It just needs to store the `parent` array for later use. This can be done by copying the input array into a member variable.

### Method `getKthAncestor(node, k)`
This method implements the upward traversal.
- It starts with the given `node`.
- It then enters a loop that runs `k` times.
- In each iteration, it updates the current node to its parent using the stored `parent` array (`node = parent[node]`).
- It also checks if the current node becomes `-1`. If it does, it means we've reached past the root before completing `k` steps, so the k-th ancestor does not exist. In this case, we return `-1` immediately.
- If the loop completes without the node becoming `-1`, the final value of `node` is the k-th ancestor.

```java
class TreeAncestor {
    int[] parent;

    public TreeAncestor(int n, int[] parent) {
        this.parent = parent;
    }

    public int getKthAncestor(int node, int k) {
        int currentNode = node;
        for (int i = 0; i < k; i++) {
            if (currentNode == -1) {
                return -1;
            }
            currentNode = this.parent[currentNode];
        }
        return currentNode;
    }
}
```
### Algorithm
- 1. In the constructor, store the `parent` array.
- 2. In `getKthAncestor(node, k)`, initialize `currentNode` to `node`.
- 3. Loop `k` times:
- 4.   If `currentNode` is `-1`, break the loop and return `-1`.
- 5.   Update `currentNode` to `parent[currentNode]`.
- 6. After the loop, return `currentNode`.

## Binary Lifting (Sparse Table)
This is a highly efficient technique that balances precomputation time with query time. The core idea is to precompute the `2^i`-th ancestor for every node `u` and for every `i` such that `2^i < n`. Any jump of size `k` can then be decomposed into a series of jumps of sizes that are powers of two. This allows us to find the k-th ancestor in logarithmic time.
**Time:** Constructor: `O(n * log n)` for precomputation to fill the `up` table. `getKthAncestor`: `O(log k)` or `O(log n)` for each query. Total for `Q` queries: `O(n * log n + Q * log n)`. This is efficient enough for the given constraints. · **Space:** `O(n * log n)` to store the `up` table.
**Pros:** Very fast query time, making it suitable for a large number of queries.; A standard and powerful technique applicable to many tree problems (like Lowest Common Ancestor).
**Cons:** Requires significant precomputation time and space compared to the brute-force approach.; More complex to understand and implement correctly.
### Explanation
### Precomputation in `TreeAncestor(n, parent)`
We use a 2D array, `up[n][LOG]`, where `LOG` is a value slightly larger than `log2(n)`. `up[u][j]` stores the `2^j`-th ancestor of node `u`. The maximum height of the tree is `n`, so we need `2^LOG > n`. A safe choice for `LOG` is `ceil(log2(n))`. For `n=50000`, `log2(50000) ≈ 15.6`, so `LOG=16` is sufficient.
- **Base Case**: The `2^0 = 1`-st ancestor of any node `u` is its direct parent. So, we initialize the first column of our table: `up[u][0] = parent[u]` for all `u`.
- **DP Calculation**: We can compute the rest of the table using the following recurrence: The `2^j`-th ancestor of `u` is the `2^(j-1)`-th ancestor of the `2^(j-1)`-th ancestor of `u`. The formula is `up[u][j] = up[ up[u][j-1] ][j-1]`. We iterate `j` from 1 to `LOG-1`, and for each `j`, we iterate `u` from 0 to `n-1`.

### Querying in `getKthAncestor(node, k)`
To find the k-th ancestor, we express `k` in binary. For example, `k=13` is `1101` in binary, which is `8 + 4 + 1`. So, to jump 13 steps, we can jump 8 steps, then 4 steps, then 1 step. We iterate from the most significant bit of `k` downwards (i.e., `j` from `LOG-1` to 0). If the `j`-th bit of `k` is set, it means we need to make a jump of size `2^j`. We update our current node: `node = up[node][j]`. If at any point `node` becomes `-1`, we know the ancestor doesn't exist, and we can return `-1`.

```java
class TreeAncestor {
    private int[][] up;
    private int LOG;

    public TreeAncestor(int n, int[] parent) {
        LOG = (int) (Math.log(n) / Math.log(2)) + 1;
        up = new int[n][LOG];

        for (int i = 0; i < n; i++) {
            up[i][0] = parent[i];
        }

        for (int j = 1; j < LOG; j++) {
            for (int i = 0; i < n; i++) {
                if (up[i][j - 1] == -1) {
                    up[i][j] = -1;
                } else {
                    up[i][j] = up[up[i][j - 1]][j - 1];
                }
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        if (node == -1) {
            return -1;
        }
        
        for (int j = LOG - 1; j >= 0; j--) {
            if ((k >> j & 1) == 1) {
                node = up[node][j];
                if (node == -1) {
                    return -1;
                }
            }
        }
        return node;
    }
}
```
### Algorithm
### Constructor
- 1. Determine `LOG`, the maximum power needed (e.g., `ceil(log2(n))`).
- 2. Create a 2D array `up[n][LOG]`.
- 3. For each node `i`, set `up[i][0] = parent[i]`.
- 4. For `j` from 1 to `LOG-1`:
- 5.   For `i` from 0 to `n-1`:
- 6.     Calculate `p = up[i][j-1]`.
- 7.     If `p` is not -1, set `up[i][j] = up[p][j-1]`, otherwise set it to -1.

### `getKthAncestor`
- 1. Initialize `currentNode` to `node`.
- 2. For `j` from `LOG-1` down to 0:
- 3.   If the `j`-th bit of `k` is 1 (i.e., `(k >> j) & 1 == 1`):
- 4.     Update `currentNode = up[currentNode][j]`.
- 5.     If `currentNode` becomes -1, return -1 immediately.
- 6. Return `currentNode`.

# Solutions
### CSharp

```csharp
public class TreeAncestor { private int [][] p ; public TreeAncestor ( int n , int [] parent ) { p = new int [ n ][]; for ( int i = 0 ; i < n ; i ++) { p [ i ] = new int [ 18 ]; for ( int j = 0 ; j < 18 ; j ++) { p [ i ][ j ] = - 1 ; } } for ( int i = 0 ; i < n ; ++ i ) { p [ i ][ 0 ] = parent [ i ]; } for ( int j = 1 ; j < 18 ; ++ j ) { for ( int i = 0 ; i < n ; ++ i ) { if ( p [ i ][ j - 1 ] == - 1 ) { continue ; } p [ i ][ j ] = p [ p [ i ][ j - 1 ]][ j - 1 ]; } } } public int GetKthAncestor ( int node , int k ) { for ( int i = 17 ; i >= 0 ; -- i ) { if ((( k >> i ) & 1 ) == 1 ) { node = p [ node ][ i ]; if ( node == - 1 ) { break ; } } } return node ; } } /** * Your TreeAncestor object will be instantiated and called as such: * TreeAncestor obj = new TreeAncestor(n, parent); * int param_1 = obj.GetKthAncestor(node,k); */
```

### Java

```java
class TreeAncestor { private int [][] p ; public TreeAncestor ( int n , int [] parent ) { p = new int [ n ][ 18 ]; for ( var e : p ) { Arrays . fill ( e , - 1 ); } for ( int i = 0 ; i < n ; ++ i ) { p [ i ][ 0 ] = parent [ i ]; } for ( int j = 1 ; j < 18 ; ++ j ) { for ( int i = 0 ; i < n ; ++ i ) { if ( p [ i ][ j - 1 ] == - 1 ) { continue ; } p [ i ][ j ] = p [ p [ i ][ j - 1 ]][ j - 1 ]; } } } public int getKthAncestor ( int node , int k ) { for ( int i = 17 ; i >= 0 ; -- i ) { if ((( k >> i ) & 1 ) == 1 ) { node = p [ node ][ i ]; if ( node == - 1 ) { break ; } } } return node ; } } /** * Your TreeAncestor object will be instantiated and called as such: * TreeAncestor obj = new TreeAncestor(n, parent); * int param_1 = obj.getKthAncestor(node,k); */
```

### CPP

```cpp
class TreeAncestor { public: TreeAncestor ( int n , vector < int >& parent ) { p = vector < vector < int >> ( n , vector < int > ( 18 , - 1 )); for ( int i = 0 ; i < n ; ++ i ) { p [ i ][ 0 ] = parent [ i ]; } for ( int j = 1 ; j < 18 ; ++ j ) { for ( int i = 0 ; i < n ; ++ i ) { if ( p [ i ][ j - 1 ] == - 1 ) { continue ; } p [ i ][ j ] = p [ p [ i ][ j - 1 ]][ j - 1 ]; } } } int getKthAncestor ( int node , int k ) { for ( int i = 17 ; ~ i ; -- i ) { if ( k >> i & 1 ) { node = p [ node ][ i ]; if ( node == - 1 ) { break ; } } } return node ; } private: vector < vector < int >> p ; }; /** * Your TreeAncestor object will be instantiated and called as such: * TreeAncestor* obj = new TreeAncestor(n, parent); * int param_1 = obj->getKthAncestor(node,k); */
```

### Python

```python
class TreeAncestor : def __init__ ( self , n : int , parent : List [ int ]): self . p = [[ - 1 ] * 18 for _ in range ( n )] for i , fa in enumerate ( parent ): self . p [ i ][ 0 ] = fa for j in range ( 1 , 18 ): for i in range ( n ): if self . p [ i ][ j - 1 ] == - 1 : continue self . p [ i ][ j ] = self . p [ self . p [ i ][ j - 1 ]][ j - 1 ] def getKthAncestor ( self , node : int , k : int ) -> int : for i in range ( 17 , - 1 , - 1 ): if k >> i & 1 : node = self . p [ node ][ i ] if node == - 1 : break return node # Your TreeAncestor object will be instantiated and called as such: # obj = TreeAncestor(n, parent) # param_1 = obj.getKthAncestor(node,k)
```