Binary search tree feature with TreeSet

The following information is for the TreeSet class in Java.

As the name suggests, this class implements a tree datastructure, achieving the complexity of O(logN) with respects to add(), remove() and contains() methods. Take the last method, contains(k), where k is the search key as an example. The implementation of TreeSet will make sure this method return True or False within O(logN).

Now if k is not in the set, one may wish to find the elements immediately on the left and right of k in the set. In other words, the result would be the same as executing binarySearch() method on the ordered list of all the elements in the set. The most efficient way I found in doing that is as follows:


left = set.headSet(k).last();
right = set.tailSet(k).first();


These will have run-time complexity of O(logN) without introducing any other datastructure (or extra memory). I've experimented with other methods such as using Iterator on the set, or ArrayList, but they all appear inferior. The reason for this efficiency seems to be the fact that eventhough headSet(k) and tailSet(k) return subsets, elements of which are only computed while using Iterators to access them. Thus, calling last() and first() on these subsets are O(1). The O(logN) comes from the search for key k, a side-effect of which are pointers to these subsets.