Ancestor Queries - Google Top Interview Questions

                        Solution in C++ :

*/
class AncestorQuerier {
    unordered_map<int, int> mp;
    vector<vector<int>> pr;

    public:
    AncestorQuerier(Tree* root) {
        int cnt = 0;
        getnodes(root, cnt);
        pr.resize(cnt + 1, vector<int>(20, -1));
        ances(root, NULL);
    }

    void getnodes(Tree* rt, int& cnt) {
        if (rt == NULL) {
            return;
        }
        cnt = cnt + 1;
        getnodes(rt->left, cnt);
        getnodes(rt->right, cnt);
    }

    void ances(Tree* src, Tree* par) {
        if (src == NULL) {
            return;
        }
        pr[src->val][0] = par ? par->val : -1;

        for (int i = 1; i < 20; i++) {
            if (pr[src->val][i - 1] != -1) {
                pr[src->val][i] = pr[pr[src->val][i - 1]][i - 1];
            } else {
                pr[src->val][i] = -1;
            }
        }

        ances(src->left, src);
        ances(src->right, src);
    }

    int getAncestor(int val, int k) {
        cout << val << " " << k << endl;
        if (val == -1 || k == 0) {
            // cout<<k<<" "<<val<<endl;
            return val;
        }
        for (int i = 19; i >= 0; i--) {
            if (k >= (1 << i)) {
                return getAncestor(pr[val][i], k - (1 << i));
            }
        }
        return -1;
    }
};
                    

                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class AncestorQuerier {
    int[][] dp;
    public AncestorQuerier(Tree root) {
        dp = new int[dfs(root) + 5][25];
        for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], -1);
        dfs(root, root);
    }
    int dfs(Tree tr) {
        if (tr == null)
            return 0;
        return dfs(tr.left) + dfs(tr.right) + 1;
    }
    void dfs(Tree root, Tree par) {
        if (root == null)
            return;
        int vr = root.val, vp = par.val;
        if (root != par) {
            dp[vr][0] = vp;
            for (int i = 1; i < 24; i++) {
                if (dp[vr][i - 1] != -1)
                    dp[vr][i] = dp[dp[vr][i - 1]][i - 1];
            }
        }
        dfs(root.left, root);
        dfs(root.right, root);
    }

    public int getAncestor(int val, int k) {
        int cur = val;
        for (int i = 0; i < 24; i++) {
            if ((k | (1 << i)) == k) {
                cur = dp[cur][i];
            }
            if (cur == -1)
                return -1;
        }
        return cur;
    }
}
                    

                        Solution in Python : 
                            
class AncestorQuerier:
    def __init__(self, root):
        self.p = {}

        def go(r, f):
            if r:
                a = self.p[r.val] = [-1] * 18
                if f:
                    a[0] = f.val
                for i in range(1, 18):
                    if a[i - 1] < 0:
                        break
                    a[i] = self.p[a[i - 1]][i - 1]
                go(r.left, r)
                go(r.right, r)

        go(root, None)

    def getAncestor(self, val, k):
        if val not in self.p:
            return -1
        for i in range(18):
            if (k >> i) & 0x01:
                val = self.p[val][i]
                if val < 0:
                    return -1
        return val