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

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?

---

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.

---

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.

---

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;
}

---

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).

---

Use an n-spaced queue for this. Whenever you find one, deque and enque,

findnth(node *root, queue q, int n, int number)
{
   if(!root || !q) 
      return;
   findnth(root->left,  q, n, number);
   if(root->d == number) {
      if(q.size() < n) {
         nth ancestor not exist;
         print q->deq() as q.size() ance return;
      }
      else
         print q.deq()
   }
   if(q.size() < n) {
      q.ins(node->data);
   }
   else {
      q.deq();q.enq(node->data);
   }
   findnth(root->right,  q, n, number);
}

---

Yes it can be done without the second pass. You just need to use two pointers. Here's how you can do it

1. Using a pointer p1,starting from the root, search for the node whose ancestor is to be found. But you go only n steps down.
2. Now when you reach n steps down, start another pointer p2 from the root, that also searches for the same node.
3. Move the both pointers in lock step, such that they both go down one level together. When p1 reaches your node, p2 will point at the nth ancestor.

---

I think this function might help ... 

function printAncestor(node *root , node *search , int *k)
{
  if(!root)
   return 0;
  if(root == search)
   return 1;

  int p1 ,p2;
  p1 = printAncestor(root->left , search , k);
  p2 = printAncestor(root->right , search , k);

 if(p1) {
   (*k)--;
if(*k >0)
   printf("%d ",root->left->value);
return 1;
 }
if(p2)
{
  (*k)--;
  if(*k >0)
  printf("%d ",root->right->value);
return 1;
}
}

The logic behind this is that , we go until the search node from the root via recursion.When we find it , we traverse along the path that it came from and print it.