Take the 2-minute tour ×

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?

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

In each node X you should store, how many nodes are in subtree with X as a root.

count(LEAF) = 1
count(NODE) = count(NODE->LEFT) + count(NODE->RIGHT) + 1

During each insert/delete you should use this equation to update counts in nodes affected by rotations.

After that solution is simple

NODE nth(NODE root, int n) {
    if (root->left->count <= n) return nth(root->left, n);
    if ( root->left->count + 1 == n) return root;
    return nth(root->right, n - root->left->count - 1);
share|improve this answer
Thanks. Actually I'm modifying the .NET SortedDictionary to be ordered, but now I see there's no easy way. –  Dmitry Fedorkov Mar 31 '12 at 8:50
add comment

you can add one attribute in each node that shows number of childrens of this node . with this attribute you can find N-th smallest node with O(lgn) .

now just you need to handle this attribute when you insert (or delete) any node into the tree. if there is no rotation then it's easy to handle but when you have rotation it's a little difficult but you can do it.

share|improve this answer
add comment

Your Answer


