Skip to main content
Talentd

Kth Ancestor of a Tree Node - Solution & Explanation

HardBinary SearchDynamic ProgrammingTreeDepth-First Search16 min readAsked at: Amazon, Goldman Sachs, Google
Practice this problem

Problem Statement

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 * 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.

Approach Overview

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.

Approach 1: Iterative Approach

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(k) for each query, as we might climb up k ancestors.
Space Complexity: O(1), aside from input storage.

Try this approach in the editor →

Approach 2: Binary Lifting Technique

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(log n) per query.
Space Complexity: O(n log n) for the precomputed table.

Try this approach in the editor →

Approach 3: Dynamic Programming + Binary Lifting

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:

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach

Time Complexity: O(k) for each query, as we might climb up k ancestors.
Space Complexity: O(1), aside from input storage.

Binary Lifting Technique

Time Complexity: O(log n) per query.
Space Complexity: O(n log n) for the precomputed table.

Dynamic Programming + Binary Lifting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Parent TraversalO(k) per queryO(n)Small k values or very few queries where preprocessing is unnecessary
Binary LiftingPreprocess: O(n log n), Query: O(log n)O(n log n)Large number of ancestor queries or deep trees requiring fast jumps

Video Solution

Binary Lifting (Kth Ancestor of a Tree Node) • Errichto Algorithms • 130,438 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Kth Ancestor of a Tree Node easy or hard?
Kth Ancestor of a Tree Node is categorized as a Hard problem because it requires preprocessing techniques like Binary Lifting and careful handling of tree ancestor relationships. The difficulty comes from designing a data structure that supports fast repeated queries.
Kth Ancestor of a Tree Node Python or Java solution
Python implementations usually store the ancestor table in a list of lists and process bits of k during queries. Java solutions use a 2D array for the jump table and iterate through powers of two. Both implementations follow the same Binary Lifting logic with O(log n) query time.
How to solve Kth Ancestor of a Tree Node in O(log n)?
Use Binary Lifting. Build a table where up[node][j] stores the 2^j-th ancestor. For a query (node, k), examine the binary representation of k and jump using the corresponding powers of two. Each jump is constant time, resulting in O(log n) query complexity.
What is the best approach for Kth Ancestor of a Tree Node?
Binary Lifting is the optimal approach. It precomputes 2^j ancestors for every node so queries can jump upward in logarithmic steps. After O(n log n) preprocessing, each query runs in O(log n) time using simple table lookups.
Is Kth Ancestor of a Tree Node asked at Google/Amazon/Meta?
Ancestor queries on trees and Binary Lifting techniques appear in interviews at companies like Google, Amazon, and Meta. Variations include Lowest Common Ancestor (LCA), k-th ancestor queries, and tree preprocessing problems that test advanced tree algorithms.
What data structure is used in Kth Ancestor of a Tree Node?
The main structure is a 2D ancestor table used for Binary Lifting. Each entry stores the 2^j-th ancestor of a node. The tree itself is typically represented using a parent array or adjacency list built with DFS or BFS.
What is the time complexity of Kth Ancestor of a Tree Node?
The naive approach takes O(k) time per query by walking up the parent chain. The optimized Binary Lifting solution performs O(n log n) preprocessing and answers each query in O(log n) time, which is efficient for large numbers of queries.

Ready to solve this problem?

Practice Kth Ancestor of a Tree Node with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Edge Weight Equilibrium Queries in a Tree