HackerRank Kth Ancestor Problem Solution

HackerRank Kth Ancestor Problem Solution

Yashwant Parihar,

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.
HackerRank Kth Ancestor Problem Solution
HackerRank Kth Ancestor Problem Solution

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)
c C# C++ HackerRank Solutions java python