Range query over binary search tree?

Okay, so does anyone know or can think of an efficient way to complete a range query over a given number range ie (x, y) in a standard binary search tree, using a minimum number of key comparisons? I wrote one that finds the minimum value <= x and then traverses the tree value by value until it finds a value that is above y, but I just realised that it would be a lot more efficient if it was recursive, and did not provide the range query's response in a sorted order.

Unfortunately, I have writer's block. Still getting used to getting my head in algorithm-space. Can anyone give me some pointers to get me started?

>>16
If you're that fucking worried about performance you shouldn't fucking be using tail recursion in Java. Sure, you'll save yourself a couple of comparisons (which isn't really where Java's going to bottleneck you anyway) in exchange for raping the fuck out of the stack because most Java VM's don't optimize tail recursion¹.

Enjoy your shitty language and malformed programming practices.

                                 
^{References: [1] http://www.ibm.com/developerworks/java/library/j-diag8.html}

>>19
THIS IS NO LAUGHING MATTER!!!
$ java -version
java version "1.5.0_14-p8"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_14-p8-root_07_may_2008_12_21)
Java HotSpot(TM) Client VM (build 1.5.0_14-p8-hark_07_may_2008_12_21, mixed mode)

$ cat TailRecursionTest.java
public class TailRecursionTest {
        private static int loop( int i ) {
                return loop( i );
        }

        public static void main( String[] args ) {
                loop( 0 );
        }
}

$ javac TailRecursionTest.java
$ java TailRecursionTest
Exception in thread "main" java.lang.StackOverflowError
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        at TailRecursionTest.loop(TailRecursionTest.java:3)
        ...