Level Ancestor Problem

The level ancestor problem is the problem of preprocessing a given rooted tree T into a data structure that can determine the ancestor of a given node at a given depth from the root of the tree. Here depth of any node in a tree is the number of edges on the shortest path from the root of the tree to the node. 
Given tree is represented as un-directed connected graph having n nodes and n-1 edges. 

The idea to solve the above query is to use Jump Pointer Algorithm and pre-processes the tree in O( n log n ) time and answer level ancestor queries in O( logn ) time. In jump pointer, there is a pointer from node N to N’s j-th ancestor, for 
j = 1, 2, 4, 8, …, and so on. We refer to these pointers as Jump_N[i], where 
Jump_u[i] = LA(N, depth(N) – 2ⁱ).

When the algorithm is asked to process a query, we repeatedly jump up the tree using these jump pointers. The number of jumps will be at most log n and therefore queries can be answered in O( logn ) time.

So we store 2ⁱth ancestor of each node and also find the depth of each node from the root of the tree. 
Now our task reduces to find the ( depth(N) – 2ⁱ )th ancestor of node N. Let’s denote X as ( depth(N) – 2ⁱ ) and let b bits of the X are set bits (1) denoted by s1, s2, s3, …sb. 
X = 2^(s1) + 2^(s2) + … + 2^(sb)

Now the problem is how to find 2^j ancestors of each node and depth of each node from the root of the tree?
Initially, we know the 2⁰th ancestor of each node is its parent. We can recursively compute 2^j-th ancestor. We know 2^j-th ancestor is 2^j-1-th ancestor of 2^j-1-th ancestor. To calculate the depth of each node we use the ancestor matrix. If we found the root node present in the array of the kth element at jth index then the depth of that node is simply 2^j but if root node doesn’t present in the array of ancestors of the kth element than the depth of kth element is 2^{( index of last non zero ancestor at kth row )} + depth of ancestor present at last index of kth row.

Below is the algorithm to fill the ancestor matrix and depth of each node using dynamic programming. Here, we denote root node as R and initially assume the ancestor of root node as 0. We also initialize depth array with -1 means the depth of the current node is not set and we need to find its depth. If the depth of the current node is not equal to -1 means we have already computed its depth.

we know the first ancestor of each node so we take j>=1,
For j>=1

ancstr[k][j] =  2jth ancestor of k    
             =  2j-1th ancestor of (2j-1th ancestor of k)       
             =  ancstr[ancstr[i][j-1][j-1]
                if ancstr[k][j] == R && depth[k] == -1
                   depth[k] = 2j
                else if ancstr[k][j] == -1 && depth[k] == -1
                   depth[k] = 2(j-1) + depth[ ancstr[k][j-1] ]
                

Let’s understand this algorithm with below diagram. 

In the given figure we need to compute 1st level ancestor of the node with value 8. First, we make ancestor matrix which stores 2^ith ancestor of nodes. Now, 2⁰ ancestor of node 8 is 10 and similarly 2⁰ ancestor of node 10 is 9 and for node 9 it is 1 and for node 1 it is 5. Based on the above algorithm 1st level ancestor of node 8 is( depth(8)-1 )th ancestor of node 8. 

We have pre computed depth of each node and depth of 8 is 5 so we finally need to find (5-1) = 4th ancestor of node 8 which is equal to 2¹th ancestor of [2¹ ancestor of node 8] and 2¹th ancestor of node 8 is 2⁰th ancestor of [2⁰th ancestor of node 8]. So, 2⁰th ancestor of [2⁰th ancestor of node 8] is node with value 9 and 2¹th ancestor of node 9 is node with value 5. Thus in this way we can compute all query in O(logn) time complexity. 

Implementation:

1th level ancestor of node 8 is = 5
2th level ancestor of node 12 is = 1
Node is not present in graph