How do I find the nth ancestor of a node in a binary search tree?

Question

I got asked this at a job interview. Here's my O(log n) solution.

Find the depth of the node. Repeat the search, but stop at depth - n.

Is there a way to do this without the second pass?

Answer 1

In your search for the node you can keep track of all nodes in the path from the current node to the root. This is a simple list with a length not greater than the depth of the tree. Once the node has been found, its nth ancestor is at position length - n in the list.

Answer 2

Just look for the node and save the path as you follow it. Roughly this (for a tree of ints):

Node* nthAncestor(Node* root, int target, int n)
{
    Node* list[n];
    int pos = 0;
    Node* node = root;
    while(node->value != target)
    {
        list[pos] = node;
        pos = (pos + 1) % n;
        if(node->value < target)
            node = node->left;
        else if(node->value > target)
            node = node->right;
    }

    return list[(pos + 1) % n];
}

Please note that I assumed the nth ancestor does exist.

For a tree of size T this runs in O(log T) time and uses O(n) space (n as in nth ancestor).

Answer 3

Your question is a bit wrong, I guess. You miss one important matter. Of course you can do it without second pass. Just maintain a queue of last n nodes in your search.

What you miss is that such algorithm needs O(log n) memory. While your solution trades off time consumption for memory usage, and uses O(1) (constant amount) of additional memory)

So your solution is not "wrong" or "too slow". It just has its own pros and cons.

Answer 4

Hmm, it occurs ot me that an easy way that requires only a single extra node or less in space would be to have a dummy node that holds the backtrack count. When you find the search target, you then set the dummy node to n and return it, not the node you found which you don't want.

You need a function DUMMY(node) that returns true only for the dummy node. (DUMMY() could be implemented by comparing the node address or by checking for a magic cookie inside the node.)

Node *search(Node *next) {
  if (found the the answer)
    dummy->backtrack = n;
    return dummy;
  } else r = search(whatever ? n->left : n->right);
  if (DUMMY(r)) {
    if (dummy->backtrack == 0)
      return next;
    --dummy->backtrack;
  }
  return r;
}