Binary lifting techique gives only Parital correct


#1
`vector<int> tree[100005];

int dp[100000][31];
set s;
int depth[100000];
int n=0;

void dfs(TreeNode *A){
if(!A) return;

int val = A->val;
s.insert(val);
n = max(n,A->val);

if(A->left){
    tree[val].push_back(A->left->val);
    tree[A->left->val].push_back(val);
    dp[A->left->val][0] = val;
    depth[A->left->val] = depth[val]+1;
    dfs(A->left);
}

if(A->right){
    tree[val].push_back(A->right->val);
    tree[A->right->val].push_back(val);
    dp[A->right->val][0] = val;
    depth[A->right->val] = depth[val]+1;
    dfs(A->right);
}

}

int lc(int a,int b){
if(depth[a] > depth[b]) swap(a,b);

int jump = depth[b] - depth[a];

for(int i=0;i<30;i++){
    if(jump&(1<<i)) b = dp[b][i];
}

if(a==b) return a;
for(int i=30;i>=0;i--){
    if(dp[a][i] != dp[b][i]){
        a = dp[a][i];
        b = dp[b][i];
    }
}

return dp[b][0];

}

int Solution::lca(TreeNode* A, int B, int C) {

if(!A) return -1;
n=0;
s.clear();

for(int i=0;i<100000;i++) {
    tree[i].clear();
}

memset(dp,0,sizeof(dp));
depth[A->val] = 1;
dfs(A);   

for(int j=1;j<30;j++){
    for(int i=1;i<=n;i++){
        dp[i][j] = dp[dp[i][j-1]][j-1];
    }
}

/*for(int i=1;i<=3;i++){
    cout<<dp[i][0]<<" "<<dp[i][1]<<'\n';
}*/
if(s.find(B)==s.end()) return -1;
    if(s.find(C)==s.end()) return -1;

if(B==C) return B;

return lc(B,C);

}`


#2

Obviously, it will, you are using DP to answer a single query. DP matrix itself takes O(NlogN) time for construction whereas simple naive approach takes O(N) time, Naive meaning moving up one by one till you find a common ancestor