Prerequisites:- DFS on Trees, Binary Lifting.
Problem :- Given an undirected connected tree with N nodes, numbered from 1 to N, and rooted at node 1, and two positive integers K and v, find the Kth ancestor (Ancestor at K level up. Parent of a node is also an ancestor 1 level up) of the node v.
Solution Approach:- The approach utilizes Binary Lifting for efficient preprocessing. The algorithm performs a Depth-First Search (DFS) to calculate the ancestors of each node and then iteratively computes the 2^{j} th ancestor based on the 2^{j-1} th ancestor using dynamic programming. For each query, the function kth ancestor efficiently jumps the given node x to its K-th ancestor by leveraging the binary representation of K. The algorithm iterates through the bits of K and performs Binary Lifting jumps accordingly. This approach ensures a logarithmic time complexity for each query, making it suitable for scenarios where multiple K-th ancestor queries need to be answered in a connected tree.
Time Complexity:
- Preprocessing:
- The preprocessing step, which includes the DFS to calculate ancestors and Binary Lifting, takes O(NlogN) time, where N is the number of nodes in the tree.
- Query (Finding K-th Ancestor):
- Each query to find the K-th ancestor takes O(logK) time, where K is the specified level of the ancestor.
Space Complexity:
- The space complexity is O(NlogN) due to the storage of ancestor information.