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

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.