1483-kth-ancestor fails 5 out of 15 test cases

[virtyaluk]

The provided code doesn't pass all the test cases:

Example: ["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"] [[4,[-1,2,3,0]],[2,3],[2,2],[2,1]]

[rishabh-vasudevan]

In the video Errichto misread 0<=parent[i]<n as 0<=parent[i]<i , therefore in his code he assumed that all the parents are smaller than that node. But that is not the case and it can be corrected by changing the order of the for loop as he had mentioned in the video before, calculating the ith ancestor of every node and then moving forward to calculate the (i+1)th ancestor for every node.

class TreeAncestor {
  int log;
  vector < vector < int >> up;
  vector < int > depth;
  public:
    TreeAncestor(int n, vector < int > & parent) {
      log = 0;

      while ((1 << log) <= n) {
        log++;
      }

      up = vector < vector < int >> (n, vector < int > (log + 1));
      depth = vector < int > (n);

      parent[0] = 0;

      for (int i = 0; i < n; i++) {
        up[i][0] = parent[i];
      }

      for (int i = 0; i < 2; i++) {
        for (int j = 1; j < n; j++) {
          depth[j] = depth[parent[j]] + 1;
        }
      }

      for (int j = 1; j <= log; j++) {
        for (int i = 0; i < n; i++) {
          up[i][j] = up[up[i][j - 1]][j - 1];
        }
      }

    }

  int getKthAncestor(int node, int k) {
    if (depth[node] < k) {
      return -1;
    }
    for (int i = 0; i <= log; i++) {
      if (k & (1 << i)) {
        node = up[node][i];
      }
    }

    return node;

  }
};

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor* obj = new TreeAncestor(n, parent);
 * int param_1 = obj->getKthAncestor(node,k);
 */

This is a similar code with the only change in the order of for loop. As of now this code passes all the test cases in LeetCode. I have calculated the depths only over 2 iterations but I think in worst case this should have been n-1 times, but that leads to time limit exceeded, that is why I have done it only 2 times.

One more approach that I found in the comment section of the youtube video is to make another node n after the last node n-1 ( as indexing is from 0 to n-1) and make the parent[0] = n and parent[n] = n. And in getKthAncestor if the node value equals n that means that ancestor does not exist and that we should return -1. This is the implementation of it.

class TreeAncestor {
  int log;
  vector < vector < int >> up;
  int number;
  public:
    TreeAncestor(int n, vector < int > & parent) {
      log = 0;
      number = n;

      while ((1 << log) <= n) {
        log++;
      }

      up = vector < vector < int >> (n+1, vector < int > (log + 1));

      parent[0] = n;
      for (int i = 0; i <= n; i++) {
        if(i == n)
            up[i][0] = n;
        else
            up[i][0] = parent[i];
      }

      for (int j = 1; j <= log; j++) {
        for (int i = 0; i <= n; i++) {
          up[i][j] = up[up[i][j - 1]][j - 1];
        }
      }

    }

  int getKthAncestor(int node, int k) {
    for (int i = 0; i <= log; i++) {
      if (k & (1 << i)) {
        node = up[node][i];
      }
    }

    if(node == number) return -1;

    return node;

  }
};

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor* obj = new TreeAncestor(n, parent);
 * int param_1 = obj->getKthAncestor(node,k);
 */

[piru72]

The first approach gives wa on

[[6,[-1,2,3,4,5,0]],[1,4]]

doing iterations 5 time to find the tree depth does the job . Although I think this solution can be hacked also . If n-1 number of iteration isn't possible we can do till 100 just to be sure .