# Finding kth ancestor in log(n) time using Binary Lifting

I am trying to solve Kth ancestor using binary lifting

But i am getting WA.

Description:
We need to solve the `kth ancestor method`, GIven a root of a tree, we need to find the kth ancestor of node.

``````class Tree
{
int N=(int)1e4+5;

int dp[][]=new int[N][31];
int parent[]=new int[N];

void dfs(Node root,int p)
{
if(root==null)
return;
parent[root.data]=p;
dfs(root.left,root.data);
dfs(root.right,root.data);
}

void construct(int u,int v)
{
dp[u][0] = v;
for(int i=1;i<31;i++)
{
dp[u][i]=dp[dp[u][i-1]][i-1];
if(dp[u][i]==-1)
break;
}
}

public int kthAncestor(Node root, int k, int node)
{
for(int i=0;i<N;i++)
Arrays.fill(dp[i],-1);

Arrays.fill(parent,-1);
dfs(root,-1);
for(int i=0;i<N;i++)
{
if(parent[i]!=-1)
construct(i,parent[i]);
}
for(int i=30;i>=0;i--)
{
if(((1<<i)&k)!=0){
node=dp[node][i];
if(node==-1)
break;
}
}
return node;
}
}
``````

Can anyone explain where i am going wrong? Thank you )
@everule1

I think the problem is that you are calling â€śconstructâ€ť in increasing order of node value, but when you call for example construct(i, parent [i]) you need all the nodes from i to root have already been built. You can include that call in the dfs function

1 Like

Thank you , yeah before we built the dp table, all its ancestors should have been built. I got the mistake. Will solve and get back to you.

My code still outputs WA, i have done what you told. I am unable to figure out:

``````                       class Tree
{
int N=(int)1e4+5;

int dp[][]=new int[N][31];

void construct(int u,int v)
{
if(v==-1)
return;
dp[u][0] = v;
for(int i=1;i<31;i++)
{
dp[u][i]=dp[dp[u][i-1]][i-1];
if(dp[u][i]==-1)
break;
}
}

void dfs(Node root,int p)
{
if(root==null)
return;
construct(root.data,p);
dfs(root.left,root.data);
dfs(root.right,root.data);
}

public int kthAncestor(Node root, int k, int node)
{
for(int i=0;i<N;i++)
Arrays.fill(dp[i],-1);

dfs(root,-1);
for(int i=30;i>=0;i--)
{
if(((1<<i)&k)!=0){
if(node==-1)
break;
}
}
return node;
}
}``````

now you are doing nothing inside the last for loop, you should be updating what â€śnodeâ€ť is

Yeah a small typo. Thank you

here is a problem on hackerrank.

my code :-

``````#include <iostream>
#include <vector>
using namespace std;
#define MaxN 100001

vector<vector<int> > tree, b_lift;
vector<bool> nodes;

void dfs(int a, int p) {
b_lift[a][0] = p;
for (int i = 1; i < 18; i++) {
b_lift[a][i] = b_lift[b_lift[a][i - 1]][i - 1];
}
//cout << p << " -> " << a << " b : "; for (int& i : b_lift[a]) cout << i << ' '; cout << '\n';
for (int& i : tree[a]) {
dfs(i , a);
}
}

void moveup(int &a, const int &k) {
for (int i = 0; i < 18; i++) {
if ((1LL << i) & k) a = b_lift[a][i];
}
}

int main () {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int T; cin >> T;
while (T--) {
tree.resize(MaxN);
b_lift.resize(MaxN, vector<int> (18, 0));
nodes.resize(MaxN, false); nodes[0] = true;
int N; cin >> N;
int x, y;
for (int i = 1; i <= N; i++) {
cin >> x >> y;
tree[y].push_back(x);
nodes[x] = true;
}
dfs(0,0);
int Q; cin >> Q;
while (Q--) {
int op; cin >> op;
if (op == 0) {
int a, b; cin >> a >> b;
tree[a].push_back(b);
dfs(b,a);
nodes[b] = true;
} else if (op == 1) {
int x; cin >> x;
nodes[x] = false;
} else {
int x, k; cin >> x >> k;
if (nodes[x] == false) {
cout << 0 << '\n';
continue;
}
moveup(x,k);
cout << x << '\n';
}
}
tree.clear();
b_lift.clear();
nodes.clear();
}
return 0;
}
``````

it is failing on 3 / 12 cases.