I agree. Let's leave this for a first cut. The recursion shouldn't cause any concurrency problems in itself, but you're right - the class is not thread safe. I will added a comment to the class doc stating this.

Two TreeSets is interesting, but to perform a bounding box search, you'd still have to perform an intersection on the two resulting sets after doing a range query.