I have a red-black tree (binary tree, all the leaves are within 2 levels). I can navigate through nodes: to left, right or parent. I know the entire count of nodes.
I have to find the N-th smallest element in a tree. Is there any way to do this faster than in O(n)? Any ideas of optimizing access by index?