Kth Ancestor of a Tree Node - Video Solutions

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.