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 JumpN[i], where
Jumpu[i] = LA(N, depth(N) – 2i).
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 2ith 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) – 2i )th ancestor of node N. Let’s denote X as ( depth(N) – 2i ) 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 2j ancestors of each node and depth of each node from the root of the tree?
Initially, we know the 20th ancestor of each node is its parent. We can recursively compute 2j-th ancestor. We know 2j-th ancestor is 2j-1-th ancestor of 2j-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 2j 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 2ith ancestor of nodes. Now, 20 ancestor of node 8 is 10 and similarly 20 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 21th ancestor of [21 ancestor of node 8] and 21th ancestor of node 8 is 20th ancestor of [20th ancestor of node 8]. So, 20th ancestor of [20th ancestor of node 8] is node with value 9 and 21th ancestor of node 9 is node with value 5. Thus in this way we can compute all query in O(logn) time complexity.
Implementation:
C++
// CPP program to implement Level Ancestor Algorithm #include <bits/stdc++.h> using namespace std; int R = 0; // n -> it represent total number of nodes // len -> it is the maximum length of array to hold // ancestor of each node. In worst case, // the highest value of ancestor a node can have is n-1. // 2 ^ len <= n-1 // len = O(log2n) int getLen( int n) { return ( int )( log (n) / log (2)) + 1; } // ancstr represents 2D matrix to hold ancestor of node. // Here we pass reference of 2D matrix so that the change // made occur directly to the original matrix // depth[] stores depth of each node // len is same as defined above // n is total nodes in graph // R represent root node void setancestor(vector<vector< int > >& ancstr, vector< int >& depth, int * node, int len, int n) { // depth of root node is set to 0 depth[R] = 0; // if depth of a node is -1 it means its depth // is not set otherwise we have computed its depth for ( int j = 1; j <= len; j++) { for ( int i = 0; i < n; i++) { ancstr[node[i]][j] = ancstr[ancstr[node[i]][j - 1]][j - 1]; // if ancestor of current node is R its height is // previously not set, then its height is 2^j if (ancstr[node[i]][j] == R && depth[node[i]] == -1) { // set the depth of ith node depth[node[i]] = pow (2, j); } // if ancestor of current node is 0 means it // does not have root node at its 2nd power // on its path so its depth is 2^(index of // last non zero ancestor means j-1) + depth // of 2^(j-1) th ancestor else if (ancstr[node[i]][j] == 0 && node[i] != R && depth[node[i]] == -1) { depth[node[i]] = pow (2, j - 1) + depth[ancstr[node[i]][j - 1]]; } } } } // c -> it represent child // p -> it represent ancestor // i -> it represent node number // p=0 means the node is root node // R represent root node // here also we pass reference of 2D matrix and depth // vector so that the change made occur directly to // the original matrix and original vector void constructGraph(vector<vector< int > >& ancstr, int * node, vector< int >& depth, int * isNode, int c, int p, int i) { // enter the node in node array // it stores all the nodes in the graph node[i] = c; // to confirm that no child node have 2 ancestors if (isNode == 0) { isNode = 1; // make ancestor of x as y ancstr[0] = p; // ifits first ancestor is root than its depth is 1 if (R == p) { depth = 1; } } return ; } // this function will delete leaf node // x is node to be deleted void removeNode(vector<vector< int > >& ancstr, int * isNode, int len, int x) { if (isNode[x] == 0) cout << "node does not present in graph " << endl; else { isNode[x] = 0; // make all ancestor of node x as 0 for ( int j = 0; j <= len; j++) { ancstr[x][j] = 0; } } return ; } // x -> it represent new node to be inserted // p -> it represent ancestor of new node void addNode(vector<vector< int > >& ancstr, vector< int >& depth, int * isNode, int len, int x, int p) { if (isNode[x] == 1) { cout << " Node is already present in array " << endl; return ; } if (isNode[p] == 0) { cout << " ancestor not does not present in an array " << endl; return ; } isNode[x] = 1; ancstr[x][0] = p; // depth of new node is 1 + depth of its ancestor depth[x] = depth[p] + 1; int j = 0; // while we don't reach root node while (ancstr[x][j] != 0) { ancstr[x][j + 1] = ancstr[ancstr[x][j]][j]; j++; } // remaining array will fill with 0 after // we find root of tree while (j <= len) { ancstr[x][j] = 0; j++; } return ; } // LA function to find Lth level ancestor of node x void LA(vector<vector< int > >& ancstr, vector< int > depth, int * isNode, int x, int L) { int j = 0; int temp = x; // to check if node is present in graph or not if (isNode[x] == 0) { cout << "Node is not present in graph " << endl; return ; } // we change L as depth of node x - int k = depth[x] - L; // int q = k; // in this loop we decrease the value of k by k/2 and // increment j by 1 after each iteration, and check for set bit // if we get set bit then we update x with jth ancestor of x // as k becomes less than or equal to zero means we // reach to kth level ancestor while (k > 0) { // to check if last bit is 1 or not if (k & 1) { x = ancstr[x][j]; } // use of shift operator to make k = k/2 // after every iteration k = k >> 1; j++; } cout << L << "th level ancestor of node " << temp << " is = " << x << endl; return ; } int main() { // n represent number of nodes int n = 12; // initialization of ancestor matrix // suppose max range of node is up to 1000 // if there are 1000 nodes than also length // of ancestor matrix will not exceed 10 vector<vector< int > > ancestor(1000, vector< int >(10)); // this vector is used to store depth of each node. vector< int > depth(1000); // fill function is used to initialize depth with -1 fill(depth.begin(), depth.end(), -1); // node array is used to store all nodes int * node = new int [1000]; // isNode is an array to check whether a // node is present in graph or not int * isNode = new int [1000]; // memset function to initialize isNode array with 0 memset (isNode, 0, 1000 * sizeof ( int )); // function to calculate len // len -> it is the maximum length of array to // hold ancestor of each node. int len = getLen(n); // R stores root node R = 2; // construction of graph // here 0 represent that the node is root node constructGraph(ancestor, node, depth, isNode, 2, 0, 0); constructGraph(ancestor, node, depth, isNode, 5, 2, 1); constructGraph(ancestor, node, depth, isNode, 3, 5, 2); constructGraph(ancestor, node, depth, isNode, 4, 5, 3); constructGraph(ancestor, node, depth, isNode, 1, 5, 4); constructGraph(ancestor, node, depth, isNode, 7, 1, 5); constructGraph(ancestor, node, depth, isNode, 9, 1, 6); constructGraph(ancestor, node, depth, isNode, 10, 9, 7); constructGraph(ancestor, node, depth, isNode, 11, 10, 8); constructGraph(ancestor, node, depth, isNode, 6, 10, 9); constructGraph(ancestor, node, depth, isNode, 8, 10, 10); // function to pre compute ancestor matrix setancestor(ancestor, depth, node, len, n); // query to get 1st level ancestor of node 8 LA(ancestor, depth, isNode, 8, 1); // add node 12 and its ancestor is 8 addNode(ancestor, depth, isNode, len, 12, 8); // query to get 2nd level ancestor of node 12 LA(ancestor, depth, isNode, 12, 2); // delete node 12 removeNode(ancestor, isNode, len, 12); // query to get 5th level ancestor of node // 12 after deletion of node LA(ancestor, depth, isNode, 12, 1); return 0; } |
Java
import java.util.*; public class LevelAncestorAlgorithm { static int R = 0 ; // Function to calculate len // len -> it is the maximum length of array to hold // ancestor of each node. static int getLen( int n) { return ( int )(Math.log(n) / Math.log( 2 )) + 1 ; } // Function to pre compute ancestor matrix static void setAncestor( int [][] ancestor, int [] depth, int [] node, int len, int n) { depth[R] = 0 ; for ( int j = 1 ; j <= len; j++) { for ( int i = 0 ; i < n; i++) { ancestor[node[i]][j] = ancestor[ancestor[node[i]][j - 1 ]] [j - 1 ]; if (ancestor[node[i]][j] == R && depth[node[i]] == - 1 ) { depth[node[i]] = ( int )Math.pow( 2 , j); } else if (ancestor[node[i]][j] == 0 && node[i] != R && depth[node[i]] == - 1 ) { depth[node[i]] = ( int )(Math.pow( 2 , j - 1 ) + depth[ancestor[node[i]] [j - 1 ]]); } } } } // Function to construct graph static void constructGraph( int [][] ancestor, int [] node, int [] depth, int [] isNode, int c, int p, int i) { node[i] = c; if (isNode == 0 ) { isNode = 1 ; ancestor[ 0 ] = p; if (R == p) { depth = 1 ; } } } // Function to remove node static void removeNode( int [][] ancestor, int [] isNode, int len, int x) { if (isNode[x] == 0 ) System.out.println( "Node does not present in graph " ); else { isNode[x] = 0 ; for ( int j = 0 ; j <= len; j++) { ancestor[x][j] = 0 ; } } } // Function to add node static void addNode( int [][] ancestor, int [] depth, int [] isNode, int len, int x, int p) { if (isNode[x] == 1 ) { System.out.println( "Node is already present in array " ); return ; } if (isNode[p] == 0 ) { System.out.println( "Ancestor does not present in an array " ); return ; } isNode[x] = 1 ; ancestor[x][ 0 ] = p; depth[x] = depth[p] + 1 ; int j = 0 ; while (ancestor[x][j] != 0 ) { ancestor[x][j + 1 ] = ancestor[ancestor[x][j]][j]; j++; } while (j <= len) { ancestor[x][j] = 0 ; j++; } } // Function to find Lth level ancestor of node x static void LA( int [][] ancestor, int [] depth, int [] isNode, int x, int L) { int j = 0 ; int temp = x; if (isNode[x] == 0 ) { System.out.println( "Node is not present in graph " ); return ; } int k = depth[x] - L; while (k > 0 ) { if ((k & 1 ) != 0 ) { x = ancestor[x][j]; } k >>= 1 ; j++; } System.out.println(L + "th level ancestor of node " + temp + " is = " + x); } public static void main(String[] args) { int n = 12 ; int [][] ancestor = new int [ 1000 ][ 10 ]; int [] depth = new int [ 1000 ]; Arrays.fill(depth, - 1 ); int [] node = new int [ 1000 ]; int [] isNode = new int [ 1000 ]; Arrays.fill(isNode, 0 ); int len = getLen(n); R = 2 ; constructGraph(ancestor, node, depth, isNode, 2 , 0 , 0 ); constructGraph(ancestor, node, depth, isNode, 5 , 2 , 1 ); constructGraph(ancestor, node, depth, isNode, 3 , 5 , 2 ); constructGraph(ancestor, node, depth, isNode, 4 , 5 , 3 ); constructGraph(ancestor, node, depth, isNode, 1 , 5 , 4 ); constructGraph(ancestor, node, depth, isNode, 7 , 1 , 5 ); constructGraph(ancestor, node, depth, isNode, 9 , 1 , 6 ); constructGraph(ancestor, node, depth, isNode, 10 , 9 , 7 ); constructGraph(ancestor, node, depth, isNode, 11 , 10 , 8 ); constructGraph(ancestor, node, depth, isNode, 6 , 10 , 9 ); constructGraph(ancestor, node, depth, isNode, 8 , 10 , 10 ); setAncestor(ancestor, depth, node, len, n); LA(ancestor, depth, isNode, 8 , 1 ); addNode(ancestor, depth, isNode, len, 12 , 8 ); LA(ancestor, depth, isNode, 12 , 2 ); removeNode(ancestor, isNode, len, 12 ); LA(ancestor, depth, isNode, 12 , 1 ); } } |
Python
import math # Global variable R representing the root node R = 0 # Function to calculate the maximum length of array to hold ancestors of each node def get_len(n): return int (math.log(n) / math.log( 2 )) + 1 # Function to precompute ancestor matrix def set_ancestor(ancstr, depth, node, length, n): # Depth of root node is set to 0 depth[R] = 0 # If depth of a node is -1, it means its depth is not set, otherwise, we have computed its depth for j in range ( 1 , length + 1 ): for i in range (n): ancstr[node[i]][j] = ancstr[ancstr[node[i]][j - 1 ]][j - 1 ] # If ancestor of the current node is R and its height is previously not set, then its height is 2^j if ancstr[node[i]][j] = = R and depth[node[i]] = = - 1 : depth[node[i]] = pow ( 2 , j) # If ancestor of the current node is 0, meaning it does not have root node at its 2^j power on its path # So its depth is 2^(index of last non-zero ancestor means j-1) + depth of 2^(j-1)th ancestor elif ancstr[node[i]][j] = = 0 and node[i] ! = R and depth[node[i]] = = - 1 : depth[node[i]] = pow ( 2 , j - 1 ) + depth[ancstr[node[i]][j - 1 ]] # Function to construct the graph def construct_graph(ancstr, node, depth, is_node, c, p, i): # Enter the node in the node array, it stores all the nodes in the graph node[i] = c # To confirm that no child node has 2 ancestors if is_node = = 0 : is_node = 1 # Make ancestor of x as y ancstr[ 0 ] = p # If its first ancestor is the root, then its depth is 1 if R = = p: depth = 1 return # Function to delete leaf node def remove_node(ancstr, is_node, length, x): if is_node[x] = = 0 : print ( "Node does not present in graph" ) else : is_node[x] = 0 # Make all ancestors of node x as 0 for j in range (length + 1 ): ancstr[x][j] = 0 return # Function to add a new node def add_node(ancstr, depth, is_node, length, x, p): if is_node[x] = = 1 : print ( "Node is already present in array" ) return if is_node[p] = = 0 : print ( "Ancestor does not present in the array" ) return is_node[x] = 1 ancstr[x][ 0 ] = p # Depth of new node is 1 + depth of its ancestor depth[x] = depth[p] + 1 j = 0 # While we don't reach the root node while ancstr[x][j] ! = 0 : ancstr[x][j + 1 ] = ancstr[ancstr[x][j]][j] j + = 1 # Remaining array will fill with 0 after we find the root of the tree while j < = length: ancstr[x][j] = 0 j + = 1 return # LA function to find Lth level ancestor of node x def LA(ancstr, depth, is_node, x, L): j = 0 temp = x # To check if the node is present in the graph or not if is_node[x] = = 0 : print ( "Node is not present in the graph" ) return # We change L as depth of node x k = depth[x] - L # In this loop, we decrease the value of k by k/2 and increment j by 1 after each iteration, # and check for set bit. If we get a set bit, then we update x with jth ancestor of x # as k becomes less than or equal to zero, meaning we reach the kth level ancestor while k > 0 : # To check if the last bit is 1 or not if k & 1 : x = ancstr[x][j] # Use of the shift operator to make k = k/2 after every iteration k = k >> 1 j + = 1 print ( "{}th level ancestor of node {} is = {}" . format (L, temp, x)) return # Main function def main(): # n represents the number of nodes n = 12 # Initialization of the ancestor matrix # Suppose max range of node is up to 1000 # If there are 1000 nodes, then also the length # of the ancestor matrix will not exceed 10 ancestor = [[ 0 ] * 10 for _ in range ( 1000 )] # This list is used to store the depth of each node depth = [ - 1 ] * 1000 # Node array is used to store all nodes node = [ 0 ] * 1000 # isNode is an array to check whether a # node is present in the graph or not is_node = [ 0 ] * 1000 # Function to calculate len # len -> it is the maximum length of array to # hold ancestor of each node. length = get_len(n) # R stores the root node global R R = 2 # Construction of the graph # Here 0 represents that the node is the root node construct_graph(ancestor, node, depth, is_node, 2 , 0 , 0 ) construct_graph(ancestor, node, depth, is_node, 5 , 2 , 1 ) construct_graph(ancestor, node, depth, is_node, 3 , 5 , 2 ) construct_graph(ancestor, node, depth, is_node, 4 , 5 , 3 ) construct_graph(ancestor, node, depth, is_node, 1 , 5 , 4 ) construct_graph(ancestor, node, depth, is_node, 7 , 1 , 5 ) construct_graph(ancestor, node, depth, is_node, 9 , 1 , 6 ) construct_graph(ancestor, node, depth, is_node, 10 , 9 , 7 ) construct_graph(ancestor, node, depth, is_node, 11 , 10 , 8 ) construct_graph(ancestor, node, depth, is_node, 6 , 10 , 9 ) construct_graph(ancestor, node, depth, is_node, 8 , 10 , 10 ) # Function to precompute ancestor matrix set_ancestor(ancestor, depth, node, length, n) # Query to get 1st level ancestor of node 8 LA(ancestor, depth, is_node, 8 , 1 ) # Add node 12 and its ancestor is 8 add_node(ancestor, depth, is_node, length, 12 , 8 ) # Query to get 2nd level ancestor of node 12 LA(ancestor, depth, is_node, 12 , 2 ) # Delete node 12 remove_node(ancestor, is_node, length, 12 ) # Query to get 5th level ancestor of node # 12 after deletion of the node LA(ancestor, depth, is_node, 12 , 1 ) if __name__ = = "__main__" : main() |
C#
using System; class LevelAncestorAlgorithm { static int R = 0; // Function to calculate the length of the array to hold ancestors static int GetLen( int n) { return ( int )(Math.Log(n) / Math.Log(2)) + 1; } // Function to precompute ancestor matrix static void SetAncestor( int [][] ancstr, int [] depth, int [] node, int len, int n) { depth[R] = 0; for ( int j = 1; j <= len; j++) { for ( int i = 0; i < n; i++) { ancstr[node[i]][j] = ancstr[ancstr[node[i]][j - 1]][j - 1]; if (ancstr[node[i]][j] == R && depth[node[i]] == -1) { depth[node[i]] = ( int )Math.Pow(2, j); } else if (ancstr[node[i]][j] == 0 && node[i] != R && depth[node[i]] == -1) { depth[node[i]] = ( int )Math.Pow(2, j - 1) + depth[ancstr[node[i]][j - 1]]; } } } } // Function to construct the graph static void ConstructGraph( int [][] ancstr, int [] node, int [] depth, int [] isNode, int c, int p, int i) { node[i] = c; if (isNode == 0) { isNode = 1; ancstr[0] = p; if (R == p) { depth = 1; } } } // Function to delete a leaf node static void RemoveNode( int [][] ancstr, int [] isNode, int len, int x) { if (isNode[x] == 0) { Console.WriteLine( "Node does not present in graph" ); } else { isNode[x] = 0; for ( int j = 0; j <= len; j++) { ancstr[x][j] = 0; } } } // Function to add a new node static void AddNode( int [][] ancstr, int [] depth, int [] isNode, int len, int x, int p) { if (isNode[x] == 1) { Console.WriteLine( "Node is already present in array" ); return ; } if (isNode[p] == 0) { Console.WriteLine( "Ancestor does not present in the array" ); return ; } isNode[x] = 1; ancstr[x][0] = p; depth[x] = depth[p] + 1; int j = 0; while (ancstr[x][j] != 0) { ancstr[x][j + 1] = ancstr[ancstr[x][j]][j]; j++; } while (j <= len) { ancstr[x][j] = 0; j++; } } // Function to find Lth level ancestor of node x static void LA( int [][] ancstr, int [] depth, int [] isNode, int x, int L) { int j = 0; int temp = x; if (isNode[x] == 0) { Console.WriteLine( "Node is not present in the graph" ); return ; } int k = depth[x] - L; while (k > 0) { if ((k & 1) == 1) { x = ancstr[x][j]; } k = k >> 1; j++; } Console.WriteLine($ "{L}th level ancestor of node {temp} is = {x}" ); } static void Main() { int n = 12; int [][] ancestor = new int [1000][]; for ( int i = 0; i < 1000; i++) { ancestor[i] = new int [10]; } int [] depth = new int [1000]; Array.Fill(depth, -1); int [] node = new int [1000]; int [] isNode = new int [1000]; Array.Clear(isNode, 0, isNode.Length); int len = GetLen(n); R = 2; ConstructGraph(ancestor, node, depth, isNode, 2, 0, 0); ConstructGraph(ancestor, node, depth, isNode, 5, 2, 1); ConstructGraph(ancestor, node, depth, isNode, 3, 5, 2); ConstructGraph(ancestor, node, depth, isNode, 4, 5, 3); ConstructGraph(ancestor, node, depth, isNode, 1, 5, 4); ConstructGraph(ancestor, node, depth, isNode, 7, 1, 5); ConstructGraph(ancestor, node, depth, isNode, 9, 1, 6); ConstructGraph(ancestor, node, depth, isNode, 10, 9, 7); ConstructGraph(ancestor, node, depth, isNode, 11, 10, 8); ConstructGraph(ancestor, node, depth, isNode, 6, 10, 9); ConstructGraph(ancestor, node, depth, isNode, 8, 10, 10); SetAncestor(ancestor, depth, node, len, n); LA(ancestor, depth, isNode, 8, 1); AddNode(ancestor, depth, isNode, len, 12, 8); LA(ancestor, depth, isNode, 12, 2); RemoveNode(ancestor, isNode, len, 12); LA(ancestor, depth, isNode, 12, 1); } } |
Javascript
// Function to calculate len // len -> it is the maximum length of array to hold // ancestor of each node. function getLen(n) { return Math.floor(Math.log(n) / Math.log(2)) + 1; } // Function to pre compute ancestor matrix function setAncestor(ancestor, depth, node, len, n) { depth[R] = 0; for (let j = 1; j <= len; j++) { for (let i = 0; i < n; i++) { ancestor[node[i]][j] = ancestor[ancestor[node[i]][j - 1]][j - 1]; if (ancestor[node[i]][j] == R && depth[node[i]] == -1) { depth[node[i]] = Math.pow(2, j); } else if (ancestor[node[i]][j] == 0 && node[i] != R && depth[node[i]] == -1) { depth[node[i]] = Math.pow(2, j - 1) + depth[ancestor[node[i]][j - 1]]; } } } } // Function to construct graph function constructGraph(ancestor, node, depth, isNode, c, p, i) { node[i] = c; if (isNode == 0) { isNode = 1; ancestor[0] = p; if (R == p) { depth = 1; } } } // Function to remove node function removeNode(ancestor, isNode, len, x) { if (isNode[x] == 0) console.log( "Node does not present in graph " ); else { isNode[x] = 0; for (let j = 0; j <= len; j++) { ancestor[x][j] = 0; } } } // Function to add node function addNode(ancestor, depth, isNode, len, x, p) { if (isNode[x] == 1) { console.log( "Node is already present in array " ); return ; } if (isNode[p] == 0) { console.log( "Ancestor does not present in an array " ); return ; } isNode[x] = 1; ancestor[x][0] = p; depth[x] = depth[p] + 1; let j = 0; while (ancestor[x][j] != 0) { ancestor[x][j + 1] = ancestor[ancestor[x][j]][j]; j++; } while (j <= len) { ancestor[x][j] = 0; j++; } } // Function to find Lth level ancestor of node x function LA(ancestor, depth, isNode, x, L) { let j = 0; let temp = x; if (isNode[x] == 0) { console.log( "Node is not present in graph " ); return ; } let k = depth[x] - L; while (k > 0) { if ((k & 1) != 0) { x = ancestor[x][j]; } k >>= 1; j++; } console.log(L + "th level ancestor of node " + temp + " is = " + x); } const n = 12; const ancestor = new Array(1000).fill(0).map(() => new Array(10).fill(0)); const depth = new Array(1000).fill(-1); const node = new Array(1000).fill(0); const isNode = new Array(1000).fill(0); const len = getLen(n); let R = 2; constructGraph(ancestor, node, depth, isNode, 2, 0, 0); constructGraph(ancestor, node, depth, isNode, 5, 2, 1); constructGraph(ancestor, node, depth, isNode, 3, 5, 2); constructGraph(ancestor, node, depth, isNode, 4, 5, 3); constructGraph(ancestor, node, depth, isNode, 1, 5, 4); constructGraph(ancestor, node, depth, isNode, 7, 1, 5); constructGraph(ancestor, node, depth, isNode, 9, 1, 6); constructGraph(ancestor, node, depth, isNode, 10, 9, 7); constructGraph(ancestor, node, depth, isNode, 11, 10, 8); constructGraph(ancestor, node, depth, isNode, 6, 10, 9); constructGraph(ancestor, node, depth, isNode, 8, 10, 10); setAncestor(ancestor, depth, node, len, n); LA(ancestor, depth, isNode, 8, 1); addNode(ancestor, depth, isNode, len, 12, 8); LA(ancestor, depth, isNode, 12, 2); removeNode(ancestor, isNode, len, 12); LA(ancestor, depth, isNode, 12, 1); |
1th level ancestor of node 8 is = 5 2th level ancestor of node 12 is = 1 Node is not present in graph