In this post, we will solve HackerRank Kth Ancestor Problem Solution.
A tree of P nodes is an un-directed connected graph having P-1 edges. Let us denote R as the root node, If A is a node such that it is at a distance of L from R. and B is a node such that it is at at distance of L + 1 from R and A is connected to B, then we call A as the parent of B.
Similarly, if A is at a distance of L from R and B is at a distance of L + K from R and there is a path of length K from A to B, then we call A as the Kth parent of B.
Susan likes to play with graphs and Tree data structure is one of her favorites. She has designed a problem and wants to know if anyone can solve it. Sometimes she adds or removes a leaf node. Your task is to figure out the Kth parent of a node at any instant.
Input Format
The first line contain an integer T denoting the number of test cases. T test cases follow. First line of each test case contains an integer P. the number of nodes in the tree. P lines follows each containing two integers X and Y separated by a single space denoting Yas the parent of X. If Y is 0, then X is the root node of the tree. (0 is for namesake and is not
in the tree).
The next line contains an integer Q, the number of queries.
Qlines follow each containing a query
- 0YX: X is added as a new leaf node whose parent is Y. X is not in the tree while Y
is in. - 1X: This tells that leaf node X is removed from the tree. X is a leaf in the tree.
2X K: In this query output the Kth parent of X. X is a node in the tree.
Note - Each node index is any number between 1 and 105 i.e., a tree with a single node can have its root indexed as 105
Sample Input
2
7
2 0
5 2
3 5
7 5
9 8
8 2
6 8
10
0 5 15
2 15 2
1 3
0 15 20
0 20 13
2 13 4
2 13 3
2 6 10
2 11 1
2 9 1
1
10000 0
3
0 10000 4
1 4
2 4 1
Sample Output
2
2
5
0
0
8
0
Explanation
There are 2 test cases. The first test case has 7 nodes with 2 as its root. There are 10 queries
- 0 5 15 -> 15 is added as a leaf node to 5.
- 2 15 2 -> 2nd parent of 15 is 15->5->2 is 2.
- 1 3 -> leaf node 3 is removed from the tree.
- 0 15 20 -> 20 is added as a leaf node to 15.
- 0 20 13 -> 13 is added as a leaf node to 20.
- 2 13 4 -> 4th parent of 13 is 2.
- 2 13 3 -> 3rd parent of 13 is 5.
- 2 6 10 -> there is no 10th parent of 6 and hence 0.
- 2 11 1 -> 11 is not a node in the tree, hence 0.
- 2 9 1 -> 9’s parent is 8.
the second testcase has a tree with only 1 node (10000).
- 0 10000 4 -> 4 is added as a leaf node to 10000.
- 1 4 -> 4 is removed.
- 2 4 1 -> as 4 is already removed, answer is 0.
Kth Ancestor C Solution
int main() {
int T,P,t,i,Q;
scanf("%d",&T);
for (t=0;t<T;t++)
{
int parent[100000+1],kth[100000+1],k[100000+1];
scanf("%d",&P);
for (i=0;i<100001;i++)
{
parent[i] = 0;
kth[i]=-1;
k[i]=-1;
}
for (i=0;i<P;i++)
{
int node,node1;
scanf("%d",&node);
scanf("%d",&parent[node]);
}
scanf("%d",&Q);
for (i=0;i<Q;i++)
{
int mode;
scanf("%d",&mode);
if (mode == 0)
{
int X,Y;
scanf("%d",&X);
scanf("%d",&Y);
parent[Y] = X;
}
else if (mode == 1)
{
int X;
scanf("%d",&X);
parent[X] = -1;
k[X]=-1;
kth[X]=-1;
}
else
{
int X,K,lv,orig;
scanf("%d",&X);
orig=X;
scanf("%d",&K);
for (lv=0;lv<K;lv++)
{
if (k[X] <= K-lv && k[X] != -1)
{
lv += k[X]-1;
X=kth[X];
continue;
}
X = parent[X];
if (X <= 0 || X > 100001)
break;
}
if (X < 0 || X > 100001)
printf("0\n",X);
else
{
printf("%d\n",X);
k[orig]=K;
kth[orig]=X;
}
}
}
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}Kth Ancestor C++ Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 111123
int dp[N][23];
vector <int> gp[N];
int parent[N], level[N];
int live[N];
int n, root;
int No;
void clear() {
for (int i = 0; i < N; i++) {
gp[i].clear();
parent[N] = -1;
live[N] = 0;
for (int j = 0; j <= 22; j++) {
dp[i][j] = -1;
}
}
}
void link(int root,int limit) {
dp[root][0] = 0;
for (int j = 1; j <= 22; j++) {
for (int i = 1; i <= limit; i++) {
if (dp[i][j-1] != -1) {
dp[i][j] = dp[dp[i][j-1]][j-1];
}
}
}
}
int kth(int num, int k) {
if (live[num] == 0) {
return 0;
}
for (int i = 0; i <= 22; i++) {
if (k & 1) {
num = dp[num][i];
}
k >>= 1;
}
return num;
}
void dfs(int node,int par,int lev) {
level[node] = lev;
for (auto v: gp[node]) {
if (v == par)continue;
dp[v][0] = node;
level[v] = level[node] + 1;
dfs(v, node , lev + 1);
}
}
void reset(int x) {
for (int i = 0; i <= 22; i++) {
dp[x][i] = -1;
level[x] = 0;
}
live[x] = 0;
}
void add(int node,int parent) {
dp[node][0] = parent;
level[node] = level[parent] + 1;
live[node] = 1;
for (int i = 1; i <= 22; i++) {
if (dp[node][i-1] != -1) {
dp[node][i] = dp[dp[node][i-1]][i-1];
}
}
}
int main() {
int t;
scanf("%d",&t);
while (t--) {
clear();
scanf("%d",&n);
No= 0;
for (int i = 0; i < n; i++) {
int p1,p2;
scanf("%d %d",&p1 ,&p2);
No = max(No,max(p1,p2));
if (p2 == 0) {
root = p1;
continue;
}
gp[p2].push_back(p1);
gp[p1].push_back(p2);
live[p1] = 1;
}
dfs(root, -1, 1);
dp[root][0] = 0;
link(root,No);
int q;
scanf("%d",&q);
while (q--) {
int type;
scanf("%d",&type);
if (type == 0) {
int x,y;
scanf("%d %d",&y, &x);
add(x,y);
}else if (type == 1) {
int x;
scanf("%d",&x);
reset(x);
}else {
int x , k;
scanf("%d %d",&x,&k);
int ans = kth(x,k);
if (ans == -1 || ans ==0) {
printf("0\n");
}else {
printf("%d\n",ans);
}
}
}
}
return 0;
}Kth Ancestor C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
class Solution {
const int EMPTY_VAL = 0;
static void Main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
var maxSize = (int)Math.Pow(10, 5) + 1;
var logN = (int)Math.Ceiling(Math.Log(maxSize, 2));
var testCount = ReadInteger();
for(var testNumber = 0; testNumber < testCount; testNumber++)
{
var nodeCount = ReadInteger();
var tree = new int[maxSize, logN];
//InitializeTree(tree);
// Load initial list of nodes
for(var nodeNumber = 0; nodeNumber < nodeCount; nodeNumber++)
{
var node = ReadNode();
tree[node.Item1, 0] = node.Item2;
}
// Fill in DP relations
InitializeRelations(tree);
//
//return;
// Load queries
var queryCount = ReadInteger();
using(var buff = new StreamWriter(Console.OpenStandardOutput(1024)))
{
Console.SetOut(buff);
for(var queryNumber = 0; queryNumber < queryCount; queryNumber++)
{
var query = ReadQuery();
switch(query[0])
{
case 0: // Add leaf
tree[query[2], 0] = query[1];
UpdateNodeRelations(tree, query[2]);
break;
case 1: // Remove leaf
InitializeNode(tree, query[1]);
//tree[query[1], 0] = EMPTY_VAL;
break;
case 2: // Find Kth parent
PrintKthParent(tree, query[1], query[2]);
break;
default: // Unknown
throw new Exception("Invalid query type.");
}
//Console.WriteLine();
//PrintTree(tree);
}
}
//PrintTree(tree);
}
}
private static void PrintTree(int [,] tree)
{
//for(var i = 0; i < tree.GetLength(0); i++)
for(var i = 0; i < 21; i++)
{
Console.Write($"{i}: ");
for(var j = 0; j < tree.GetLength(1); j++)
{
Console.Write($"{tree[i, j]} ");
}
Console.WriteLine();
}
}
private static void InitializeRelations(int [,] tree)
{
for(var j = 1; j < tree.GetLength(1); j++)
{
for(var i = 1; i < tree.GetLength(0); i++)
{
var currentAncestor = tree[i, j - 1];
// Skip indexes without parents
// If we wanted to, we could have kept a dense array
// of populated indexes, rather than iterating over the
// entire set of possible indexes
if(currentAncestor <= 0)
{
continue;
}
var nextAncestor = tree[currentAncestor, j - 1];
// Skip the rest of the index, if we've reached the end
if(nextAncestor <= 0)
{
continue;
}
tree[i, j] = nextAncestor;
}
}
}
private static void UpdateNodeRelations(int[,] tree, int node)
{
for(var j = 1; j < tree.GetLength(1); j++)
{
var nextAncestor = tree[tree[node, j - 1], j - 1];
if(nextAncestor <= 0)
{
break;
}
tree[node, j] = nextAncestor;
}
}
private static void InitializeTree(int[,] tree)
{
for(int i = 0; i < tree.GetLength(0); i++)
{
InitializeNode(tree, i);
}
}
private static void InitializeNode(int[,] tree, int node)
{
for(var i = 0; i < tree.GetLength(1); i++)
{
tree[node, i] = EMPTY_VAL;
}
}
private static void PrintKthParent(int[,] tree, int node, int k)
{
// a -> b -> c -> d
// a[0] = b
// a[1] = c
// b[0] = c
// b[1] = d
// c[0] = d
// d[0] = 0
// Relation tree[i, j] = tree[tree[i, j - 1], j - 1], if RHS > 0
var current = node;
var j = 0;
var len = tree.GetLength(1);
for(var x = 1; current > 0 && x <= k && j < len; x <<= 1, j++)
{
//Console.WriteLine($"j = {j}, k = {k}, current = {current}");
if((k & x) == x)
{
current = tree[current, j];
//Console.WriteLine($"New current = {current}");
}
}
//current = Math.Max(0, current);
Console.WriteLine(current);
}
private static int[] ReadQuery()
{
var line = Console.ReadLine();
var split = line.Split(' ');
var result = new int[split.Length];
for(var i = 0; i < split.Length; i++)
{
result[i] = Int32.Parse(split[i]);
}
return result;
}
private static int ReadInteger()
{
return Int32.Parse(Console.ReadLine());
}
private static (int, int) ReadNode()
{
var line = Console.ReadLine();
var split = line.Split(' ');
return (Int32.Parse(split[0]), Int32.Parse(split[1]));
}
}Kth Ancestor Java Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
for(int T = ni(); T >= 1;T--){
int n = 100001;
int m = ni();
int[] from = new int[m];
int[] to = new int[m];
for(int i = 0;i < m;i++){
from[i] = ni();
to[i] = ni();
}
int[][] g = packU(n, from, to);
int[] par = parents(g, 0);
int[][] spar = new int[17][n];
for(int i = 0;i < n;i++){
spar[0][i] = par[i];
}
for(int d = 1;d < 17;d++){
for(int i = 0;i < n;i++){
spar[d][i] = spar[d-1][i] == -1 ? -1 : spar[d-1][spar[d-1][i]];
}
}
int Q = ni();
for(int z = 0;z < Q;z++){
int type = ni();
if(type == 0){
// insert
int y = ni(), x = ni();
spar[0][x] = y;
for(int d = 1;d < 17;d++){
spar[d][x] = spar[d-1][x] == -1 ? -1 : spar[d-1][spar[d-1][x]];
}
}else if(type == 1){
// remove
int y = ni();
for(int d = 0;d < 17;d++){
spar[d][y] = -1;
}
}else if(type == 2){
// kth
int y = ni(), K = ni();
for(int d = 0;d < 17;d++){
if(K<<31-d<0){
y = spar[d][y];
if(y == -1)break;
}
}
if(y == -1)y = 0;
out.println(y);
}
}
}
}
static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for(int f : from)
p[f]++;
for(int t : to)
p[t]++;
for(int i = 0;i < n;i++)
g[i] = new int[p[i]];
for(int i = 0;i < from.length;i++){
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
public static int[] parents(int[][] g, int root)
{
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] q = new int[n];
q[0] = root;
for(int p = 0, r = 1;p < r;p++) {
int cur = q[p];
for(int nex : g[cur]){
if(par[cur] != nex){
q[r++] = nex;
par[nex] = cur;
}
}
}
return par;
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Kth Ancestor Python Solution
import sys
import math
from typing import Deque
sys.setrecursionlimit(1000000)
class Node:
def __init__(self, i, depth, children, ancestors):
self.i = i
self.depth = depth
self.children = set(children)
self.ancestors = list(ancestors)
def print_graph(G):
for X in G:
node = G[X]
print(node)
print()
def dfs(G, u):
node = G[u]
if node.ancestors[0] != 0:
log = math.floor(math.log(node.depth, 2))
for i in range(1, log + 1):
ancestor = G[node.ancestors[i - 1]]
if not len(ancestor.ancestors) > i - 1:
break
node.ancestors.append(ancestor.ancestors[i - 1])
for v in node.children:
child = G[v]
child.depth = node.depth + 1
dfs(G, v)
def dfs_stack(G, u):
stack = Deque([u])
while stack:
u = stack.pop()
node = G[u]
if node.ancestors[0] != 0:
log = math.floor(math.log(node.depth, 2))
for i in range(1, log + 1):
ancestor = G[node.ancestors[i - 1]]
if not len(ancestor.ancestors) > i - 1:
break
node.ancestors.append(ancestor.ancestors[i - 1])
for v in node.children:
child = G[v]
child.depth = node.depth + 1
stack.append(v)
T = int(sys.stdin.readline())
for _ in range(T):
P = int(sys.stdin.readline())
S = set()
#G = {}
G = [None] * 100001
for _ in range(P):
X, Y = list(map(int, sys.stdin.readline().strip().split(' ')))
S.add(X)
if Y == 0:
G[X] = Node(X, 0, [], [0])
else:
G[X] = Node(X, 0, [], [Y])
root = None
#for X in G:
for X in S:
node = G[X]
if node.ancestors[0] != 0:
parent = G[node.ancestors[0]]
parent.children.add(X)
else:
root = X
#print_graph(G)
#G[0] = Node(0, 0, [], [0])
dfs_stack(G, root)
#print_graph(G)
Q = int(sys.stdin.readline())
for _ in range(Q):
q = list(map(int, sys.stdin.readline().strip().split(' ')))
if q[0] == 0:
Y, X = q[1:]
parent = G[Y]
#parent.children.add(X)
node = Node(X, parent.depth + 1, [], [Y])
G[X] = node
dfs_stack(G, X)
#print_graph(G)
elif q[0] == 1:
X = q[1]
node = G[X]
#if node.ancestors[0] != 0:
# parent = G[node.ancestors[0]]
# parent.children.remove(X)
G[X] = None
#G.pop(X)
#print_graph(G)
elif q[0] == 2:
X, K = q[1:]
a = 0
#if X in G:
if G[X] is not None:
node = G[X]
k = K
while k > 0:
log = math.floor(math.log(k, 2))
if not len(node.ancestors) > log or not node.ancestors[log] != 0:
a = 0
break
node = G[node.ancestors[log]]
a = node.i
k -= 2 ** log
print(a)
