Binary search tree filter values in a range

Question

I have a tree(RBT) consisting of N elements. Let's imagine I have this tree (N = 7):

           4
    2             6
1       3      5     7

How do I filter values in some range (e.g. print all values between 3 and 6) with better performance than O(N)?

Is there any specific algorithm? I'm imagining it something like find position of value 3 [log(N)], somehow continue until you get to the 6 [O(M)].

Answer 1

If you have Sedgevick's Algorithms, 4 ed., look at the end of chapter 3.2 on BST's. Also book companion has implementation in Java.

Basic algorithm is very simple: do recursive inorder traversal of the tree. Put keys in the left subtree in the queue (or whatever container), then key at root, then all keys in the right subtree. Add only keys that are in specified range, and skip recursive calls for subtrees that cannot contain keys in range.

You can try this here - this is a basic BST (range queries work the same in RBT) with getting values between 3 and 6.

Algorithm itself:

public IEnumerable<T> Keys(T low, T high)
{
    var queue = new Queue<T>();
    Keys(Root, queue, low, high);
    return queue;
}

private void Keys(Node node, Queue<T> queue, T low, T high)
{
    if (node == null)
        return;

    int cmpLow = low.CompareTo(node.Key);
    int cmpHigh = high.CompareTo(node.Key);

    if (cmpLow < 0)
    {
        Keys(node.Left, queue, low, high);
    }
    if (cmpLow <= 0 && cmpHigh >= 0)
    {
        queue.Enqueue(node.Key);
    }    
    if (cmpHigh > 0)
    {
        Keys(node.Right, queue, low, high);
    }
}

Complexity should be O(h + k), where h is height of the tree and k is number of values in range. Also have a look at Range Tree datastructre that is good at ranges.