Hi. I'm trying to figure out a problem from my homework. Its about Red-Black trees. Also, this can be used for a regular BST.

Heres the problem, I have to come up with an algorithm that finds the n-th element in the Red-Black tree. My teacher said that it should be O(log n), but the best I can think of is O(n). The way I was thinking was doing an ordered search and place each key into an array, and return the n-th one.

I've been thinking all weekend on how to do this in O(log n), but have thought of nothing. I think its impossible since you have to figure out the keys position in the tree, but you have to look at all keys to do this. Like, you just cant start at the root, and from there knowing what index you are looking for, make the right choice on either left or right, then somehow getting to the correct spot.

Anyone have any ideas on how to do this one? I'm stumped