The "Kth Ancestor of a Tree Node" problem asks you to efficiently answer queries about the ancestry of nodes in a rooted tree. You are given a tree with n nodes, labeled from 0 to n-1, where node 0 is the root. The parent of each node is provided in an array parent, where parent[i] is the parent of node i (with parent[0] = -1 for the root).
You must implement a class with two methods:
KthAncestor(int n, int[] parent): Constructor to initialize the tree.getKthAncestor(int node, int k): Returns the k-th ancestor of node, or -1 if such ancestor does not exist.node and k will be made.O(log n) time per query).
The naive approach to this problem would be, for each query, to walk up the tree from the given node to its parent, repeating this process k times. However, this can be slow if k is large or if there are many queries, since each step takes O(1) and up to O(k) per query.
To optimize, we look for a way to "jump" up the tree in bigger strides. This is similar to how binary search jumps by powers of two. If we preprocess and store, for each node, its 2j-th ancestor for all valid j, we can decompose any k as a sum of powers of two, and answer each query in O(log k) time. This technique is known as binary lifting.
The challenge is to preprocess the ancestors efficiently and use them for fast queries.
We use the binary lifting technique to preprocess and answer queries efficiently. Here's how:
j such that 2j <= n.node is the 2j-1-th ancestor of its 2j-1-th ancestor.up[node][j] where up[node][j] is the 2j-th ancestor of node.k-th ancestor, we look at the binary representation of k.k, we "jump" up by the corresponding power of two using our table.-1), we return -1.O(log n) time, since k can be at most n and we only need to check up to log n bits.O(n log n) time and space, which is efficient for large trees and many queries.
Suppose n = 7 and parent = [-1,0,0,1,1,2,2], giving this tree:
getKthAncestor(5, 2):
10, so only the 21 bit is set.up[5][1] is the ancestor 2 steps above 5.up[5][0] = 2 (parent), up[5][1] = 0 (grandparent).0.getKthAncestor(3, 3):
11, so both 20 and 21 bits are set.up[3][1] = 0.up[0][0] = -1 (root has no parent).-1.O(k) (walk up the tree k times)O(n) (just the parent array)O(n log n) (for each node, compute up to log n ancestors)O(log k) (or O(log n), since k can be at most n)O(n log n) (for the ancestor table)
The optimized approach is much faster for large k and many queries.
The "Kth Ancestor of a Tree Node" problem is a classic example of using binary lifting to efficiently answer ancestry queries in a tree. By preprocessing each node's ancestors at powers of two, we can quickly "jump" up the tree in logarithmic time per query. This approach is both elegant and practical, making it ideal for problems with many queries and large trees.
class TreeAncestor:
def __init__(self, n: int, parent: list[int]):
LOG = 0
tmp = n
while tmp:
LOG += 1
tmp //= 2
self.LOG = LOG
self.up = [[-1] * LOG for _ in range(n)]
for v in range(n):
self.up[v][0] = parent[v]
for j in range(1, LOG):
for v in range(n):
if self.up[v][j-1] != -1:
self.up[v][j] = self.up[self.up[v][j-1]][j-1]
def getKthAncestor(self, node: int, k: int) -> int:
for j in range(self.LOG):
if k & (1 << j):
node = self.up[node][j]
if node == -1:
return -1
return node
class TreeAncestor {
vector<vector<int>> up;
int LOG;
public:
TreeAncestor(int n, vector<int>& parent) {
LOG = 0;
int tmp = n;
while (tmp) {
LOG++;
tmp /= 2;
}
up.assign(n, vector<int>(LOG, -1));
for (int v = 0; v < n; ++v)
up[v][0] = parent[v];
for (int j = 1; j < LOG; ++j)
for (int v = 0; v < n; ++v)
if (up[v][j-1] != -1)
up[v][j] = up[up[v][j-1]][j-1];
}
int getKthAncestor(int node, int k) {
for (int j = 0; j < LOG; ++j) {
if (k & (1 << j)) {
node = up[node][j];
if (node == -1)
return -1;
}
}
return node;
}
};
class TreeAncestor {
int[][] up;
int LOG;
public TreeAncestor(int n, int[] parent) {
LOG = 1;
int tmp = n;
while (tmp > 1) {
LOG++;
tmp /= 2;
}
up = new int[n][LOG];
for (int v = 0; v < n; ++v)
up[v][0] = parent[v];
for (int j = 1; j < LOG; ++j)
for (int v = 0; v < n; ++v)
up[v][j] = up[v][j-1] == -1 ? -1 : up[up[v][j-1]][j-1];
}
public int getKthAncestor(int node, int k) {
for (int j = 0; j < LOG; ++j) {
if ((k & (1 << j)) != 0) {
node = up[node][j];
if (node == -1)
return -1;
}
}
return node;
}
}
var TreeAncestor = function(n, parent) {
this.LOG = 0;
let tmp = n;
while (tmp) {
this.LOG++;
tmp = Math.floor(tmp / 2);
}
this.up = Array.from({length: n}, () => Array(this.LOG).fill(-1));
for (let v = 0; v < n; ++v)
this.up[v][0] = parent[v];
for (let j = 1; j < this.LOG; ++j)
for (let v = 0; v < n; ++v)
if (this.up[v][j-1] !== -1)
this.up[v][j] = this.up[this.up[v][j-1]][j-1];
};
TreeAncestor.prototype.getKthAncestor = function(node, k) {
for (let j = 0; j < this.LOG; ++j) {
if (k & (1 << j)) {
node = this.up[node][j];
if (node === -1)
return -1;
}
}
return node;
};