Last Updated: 8 Jul, 2021
Ninja And Numbers
Moderate
Asked in companies
Ninja is learning tree data structures. His friend is helping him learn by giving him problems to solve. He gives him 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 the ith node. The root of the tree is node 0. Now Ninja has to 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.
Input Format:
The first line of input contains a single integer ‘T’, denoting the number of test cases.
The second line of each test case contains a positive integer ‘N’, denoting the number of nodes.
The third line of each test case contains the parent array.
The fourth line of each test case contains a node value and k value.
Output Format :
The first and only line of each test case contains an integer denoting the kth ancestor.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= k <= N <= 5 * 10 ^ 4
0 <= node < N
0 <= parent[i] < N
Time limit: 1 second
Approaches
This problem can be solved using a technique known as binary lifting. We need to compute each node, which is exactly 2^i nodes above a given node, and we will store it in an array up[node][i]. Now we will run a DFS to fill this for each node. To compute up[node][i], we can find the node which is 2^i-1 steps above the node which is 2^i - 1 above the current node, hence up[node][i] = up[up[node][i-1]][i-1]. Each query can be answered in log n by treating k as a binary number and moving 2^i steps upward for each set bit in k.
The steps are as follows:
- Initialize vector graphs to store the edges of the tree.
- Run a loop from i =1 to i = N - 1:
- Initialize u with parent[i] to store the parent node of the current node.
- Store in graph[u] the current node i.
- Perform a recursive function dfs on this tree.
- Store a pointer p = -1 to indicate it is the root node.
- If p is not -1then store in par[src][[0], the value of p.par signifies the ith ancestor of a given node ‘src’.
- Then run a loop from j = 1 to (1<<j) <=h:
- Store in par[src][j] the value of par[par[src][j-1]][j-1].
- We iterate over all the child nodes of the present node and recursively perform dfs.
- We call the function getKthAncestor to get the kth ancestor.
- We run a loop from i = 31 to 0:
- If the value of the node is -1, then break
- If (1<<i)&k then we sore the value par[node][i] in node.
- Finally, we return the node, which is the kth ancestor.
Here we first traverse the binary tree and store the ancestor of each node in an array of size n. For example, suppose the array is parent[n]. Then at index i, parent[i] will store the parent of the ith node. So, the 2nd ancestor of the ith node will be parent[parent[i]] and so on. We will use this idea to calculate the kth ancestor of the given node. We can use level order traversal to populate this array.
The steps are as follows:
- Initialize an array ‘ancestors’ to store the ancestors of a given node.
- Initialize a root pointer to point to the tree’s root, which we will create from the ‘parents’ array.
- Run a loop from i =1 to i = N - 1:
- Initialize root with parent[i] to store the parent node of the current node.
- Store in the left subtree the value of parents[2*1] and store in the right subtree the value of parents[2*1 + 1].
- We pass the root of the given nodes and ‘ancestors’, which will return the ‘ancestors’ array containing the nodes of a given node.
- For root, the parent will be -1, so we store -1 in the ‘ancestors’ array for root.
- We initialize a queue to store the nodes.
- We push ‘root’ in the queue.
- We run a while loop with the condition the queue is not empty.
- We initialize a temporary pointer ‘temp’ and store the front element of the queue in it, and pop the front element.
- If the node to the left of the present is not null, then store in ancestors[temp -> left -> data] the value of the node ‘temp’ and push the value of temp->left in the queue.
- if the node to the right of the present is not null, then store in ancestors[temp -> right -> data] the value of the node ‘temp’ and push the value of temp->right in the queue.
- We run a while loop till the value of the given node doesn’t become -1:
- We find the parent of ‘node’ by looking up in the ‘ancestors’ array by using ancestors[node] and then store the value of the parent in ‘node’ itself and simultaneously increment the value of a counter ‘count’.
- If the value of ‘count’ becomes equal to K, we break out of the loop.
- We return the value of ‘node’ as our final answer.