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:
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 * 104parent.length == nparent[0] == -10 <= parent[i] < n for all 0 < i < n0 <= node < n5 * 104 queries.Problem Overview: You are given a rooted tree where each node knows its direct parent. The task is to design a data structure that answers queries of the form: what is the k-th ancestor of node v? If the ancestor does not exist, return -1. The challenge is handling many queries efficiently.
Approach 1: Iterative Parent Traversal (O(k) time per query, O(n) space)
The simplest idea is to repeatedly move up the tree using the parent pointer. Starting from node v, follow parent[v] exactly k times. If you reach -1 before finishing the steps, the ancestor does not exist. This approach stores the parent array directly and performs a loop for each query.
This method is easy to implement and works well when k is small or when the number of queries is limited. However, if the tree height is large or queries frequently request large k, the runtime becomes expensive because every query may walk many edges upward. Time complexity is O(k) per query and space complexity is O(n) for storing the parent references.
Approach 2: Binary Lifting Technique (Preprocess O(n log n), Query O(log n), Space O(n log n))
Binary lifting speeds up ancestor jumps by precomputing powers of two. Instead of only storing the direct parent, maintain a table up[node][j] representing the 2^j-th ancestor of each node. The table is built using dynamic programming: the 2^j-th ancestor equals the 2^(j-1)-th ancestor of the 2^(j-1)-th ancestor.
During a query, decompose k into powers of two. For every set bit in k, jump upward using the corresponding precomputed ancestor. For example, if k = 13, move 2^3, then 2^2, then 2^0. Each jump is a constant-time table lookup, so the entire query runs in O(log n).
This technique is widely used in tree problems involving repeated ancestor queries. Precomputation typically uses a DFS or BFS traversal to establish depths and parent relationships, which connects it to concepts from depth-first search and dynamic programming. The extra preprocessing cost pays off when handling thousands of queries.
Recommended for interviews: Interviewers expect the Binary Lifting solution. The iterative traversal demonstrates baseline understanding of parent relationships, but it does not scale well for repeated queries. Binary lifting shows you understand tree preprocessing, bit decomposition, and efficient query design—skills commonly tested in hard tree problems.
In this iterative approach, the idea is to climb up the tree by following the parent links step-by-step. This means starting from the given node, and for each step, move to the parent of the current node. Repeat this process k times or until the root is reached.
We initialize the TreeAncestor class by storing the parent array. In the getKthAncestor() method, we iteratively update the node by assigning it to its parent, decrementing k at each step until k becomes zero or the node becomes -1, indicating the root or beyond.
Time Complexity: O(k) for each query, as we might climb up k ancestors.
Space Complexity: O(1), aside from input storage.
The binary lifting technique involves preprocessing each node to precompute its 2ith ancestors for efficiency. This allows us to compute large jumps in the tree, significantly reducing query times by utilizing precomputed ancestors at various power levels of 2.
We use a 2D array up to store precomputed ancestors. We initialize with each node’s direct parent and build up to higher powers of two. During a query, we traverse the precomputed table using the bits of k to jump as far up the tree as possible.
Java
JavaScript
Time Complexity: O(log n) per query.
Space Complexity: O(n log n) for the precomputed table.
The problem asks us to find the k-th ancestor node of a node node. If we solve it by brute force, we need to traverse upwards from node for k times, which has a time complexity of O(k) and will obviously exceed the time limit.
We can use dynamic programming combined with the idea of binary lifting to handle this.
We define p[i][j] as the 2^j-th ancestor node of node i, i.e., the node reached by moving 2^j steps upwards from node i. Then we can get the state transition equation:
$
p[i][j] = p[p[i][j-1]][j-1]
That is, to find the 2^j-th ancestor node of node i, we can first find the 2^{j-1}-th ancestor node of node i, and then find the 2^{j-1}-th ancestor node of this node. Therefore, we need to find the ancestor node of each node at a distance of 2^j, until we reach the maximum height of the tree.
For each query later, we can decompose k into its binary representation, and then according to the positions of 1 in the binary, we accumulate the queries upwards, and finally get the k-th ancestor node of node node.
In terms of time complexity, the initialization is O(n times log n), and the query is O(log n). The space complexity is O(n times log n), where n$ is the number of nodes in the tree.
Similar problems:
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(k) for each query, as we might climb up k ancestors. |
| Binary Lifting Technique | Time Complexity: O(log n) per query. |
| Dynamic Programming + Binary Lifting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Parent Traversal | O(k) per query | O(n) | Small k values or very few queries where preprocessing is unnecessary |
| Binary Lifting | Preprocess: O(n log n), Query: O(log n) | O(n log n) | Large number of ancestor queries or deep trees requiring fast jumps |
Binary Lifting (Kth Ancestor of a Tree Node) • Errichto Algorithms • 123,968 views views
Watch 9 more video solutions →Practice Kth Ancestor of a Tree Node with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor