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

Question

I was asked for an interview. Here is my solution O(log n) .

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

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

Answer 1

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

Answer 2

Just find the node and save the path following it. Roughly this (for the ints tree):

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

Note that I suggested that the nth ancestor really exists.

For a tree of size T, this is done in O(log T) time and uses the space O(n) (n like the nth ancestor).

Answer 3

Your question is a little wrong, I think. You are missing one important question. Of course, you can do this without a second pass. Just save the queue of the last n nodes in your search.

What you will miss is that this algorithm requires O(log n) memory. Although your solution distracts the time consuming memory usage and uses O(1) (constant amount) of extra memory)

So your decision is not "wrong" or "too slow." He just has its pros and cons.

Answer 4

Hmm, it seems to me that a simple way that requires only one extra node or less in space would have a dummy node that contains a countdown counter. When you find the search target, you set the dummy node to n and return it, not the node you don't want.

You need a DUMMY(node) function that returns true only for a dummy node. ( DUMMY() can be implemented by comparing the node address or by checking for the 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; } 

Answer 5

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

Answer 6

Yes, this can be done without a second pass. You just need to use two pointers. Here is how you can do it.

• Using the p1 pointer, starting at the root, find the node whose ancestor should be found. But you only take n steps down.
• Now that you have reached n steps down, start another pointer p2 from the root, which is also looking for the same node.
• Move both pointers in the lock step so that they both go down one level together. When p1 reaches your node, p2 will point to the nth ancestor.

Answer 7

 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 before finding the node from the root through recursion. When we find him, we follow the path from which he came, and print it.