TreeSet

This topic introduces TreeSet, a popular implementation of the NavigableSet interface in Java. Like other Set implementations, TreeSet stores only unique elements, but it also maintains elements in a sorted order. In this topic, we'll explore how TreeSet works, its key features, constructors, methods, and limitations.

TreeSet behavior

TreeSet is a sorted collection that does not allow duplicates and organizes its elements in natural order (or using a specified comparator). Internally, it is backed by a TreeMap, which in turn, is implemented using a red-black tree — a type of self-balancing binary search tree.

This structure enables efficient $O(\log n)$ time complexity for basic operations like add, remove, and contains.

Let's look at a simple example:

public class TreeSetDemo {
    public static void main(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("J. Bloch");
        set.add("J. Gosling");
        set.add("B. Eckel");
        set.add("J. Bloch"); // duplicate

        System.out.println(set); // [B. Eckel, J. Bloch, J. Gosling]
    }
}

As seen above, TreeSet automatically arranges elements in ascending order and does not include duplicates.

Here are the key characteristics of TreeSet:

• TreeSet contains only unique elements — no duplicates allowed.

• Elements are sorted in natural order (or by a comparator).

• null values are generally not permitted, especially when using natural ordering.

• Provides $O(\log n)$ time complexity for basic operations (add, remove, contains).

• TreeSet is not synchronized, which means it is not safe to use directly in multithreaded environments. To make it thread-safe, you can wrap it using Collections.synchronizedNavigableSet():

  NavigableSet<String> syncNavSet = Collections.synchronizedNavigableSet(new TreeSet<>());
  

  This wrapper ensures that all access to the set is synchronized, and also retains the full API of NavigableSet.

• Does not maintain insertion order — it maintains sorted order.

Constructors

TreeSet provides several constructors, including:

public TreeSet()
public TreeSet(Collection<? extends E> c)
public TreeSet(Comparator<? super E> comparator)
public TreeSet(SortedSet<E> s)

Here are some examples of how to use them:

1. Default constructor
Creates an empty TreeSet that sorts elements in their natural order:

Set<String> set = new TreeSet<>();
set.add("C");
set.add("A");
set.add("B");
System.out.println(set); // [A, B, C]

2. Constructor with a collection
Creates a TreeSet with elements from another collection:

List<String> list = List.of("Mercury", "Venus", "Earth", "Earth");
Set<String> set = new TreeSet<>(list);
System.out.println(set); // [Earth, Mercury, Venus]

3. Constructor with comparator
You can define your own custom sorting using a Comparator:

Set<String> set = new TreeSet<>(Comparator.reverseOrder());
set.add("Apple");
set.add("Banana");
set.add("Cherry");
System.out.println(set); // [Cherry, Banana, Apple]

Methods

TreeSet implements both the SortedSet and NavigableSet interfaces. Here are the most commonly used methods from each:

SortedSet methods:

• add(E e): Adds the element if it's not already present.

• contains(Object o): Returns true if the element is in the set.

• remove(Object o): Removes the specified element if it is present.

• isEmpty(): Returns true if the set is empty.

• size(): Returns the number of elements.

• clear(): Removes all elements from the set.

• toArray(): Converts the set into an array.

• iterator(): Returns an iterator over elements in ascending order, according to the set's ordering.

NavigableSet methods:

• first(): Returns the lowest element, according to the set's ordering (natural or comparator-based).

• last(): Returns the highest element, according to the set's ordering (natural or comparator-based).

• higher(E e): Returns the least element strictly greater than the given element.

• lower(E e): Returns the greatest element strictly less than the given element.

• ceiling(E e): Returns the least element greater than or equal to the given element.

• floor(E e): Returns the greatest element less than or equal to the given element.

Let's look at a few in action:

Set<Integer> set = new TreeSet<>();
set.add(10);
set.add(5);
set.add(20);

System.out.println(set.contains(10)); // true
System.out.println(set.size()); // 3
System.out.println(set); // [5, 10, 20]

Accessing specific elements

TreeSet offers useful methods to find elements relative to others:

TreeSet<Integer> numbers = new TreeSet<>();
numbers.addAll(List.of(10, 20, 30, 40));

System.out.println(numbers.higher(20));  // 30
System.out.println(numbers.lower(20));   // 10
System.out.println(numbers.ceiling(20)); // 20
System.out.println(numbers.floor(25));   // 20
System.out.println(numbers.first());     // 10
System.out.println(numbers.last());      // 40

Iteration

You can iterate over a TreeSet using a standard for-each loop or an Iterator.

TreeSet<String> planets = new TreeSet<>();
planets.add("Earth");
planets.add("Mars");
planets.add("Venus");

for (String planet : planets) {
    System.out.println(planet);
}

This will output:

Earth
Mars
Venus

Remember, the order is sorted, not insertion-based.

Working with null values

Unlike HashSet, TreeSet does not allow null elements, when using natural ordering. This is because null cannot be compared to other elements using the compareTo() method, and attempting to insert it will result in a NullPointerException.

However, TreeSet can store null elements if a comparator is provided that explicitly defines how to handle them during comparisons. Java provides built-in comparators like Comparator.nullsFirst() and Comparator.nullsLast() to help with this:

• Comparator.nullsFirst(): Treats null as less than any non-null element, placing it at the beginning of the set.

• Comparator.nullsLast(): Treats null as greater than any non-null element, placing it at the end of the set.

Here's how to use these comparators in a TreeSet:

Set<String> set1 = new TreeSet<>(Comparator.nullsFirst(Comparator.naturalOrder()));
set1.add(null);
set1.add("Apple");
set1.add("Banana");
System.out.println(set1); // [null, Apple, Banana]

Set<String> set2 = new TreeSet<>(Comparator.nullsLast(Comparator.naturalOrder()));
set2.add(null);
set2.add("Apple");
set2.add("Banana");
System.out.println(set2); // [Apple, Banana, null]

You can also define a custom comparator for handling null in a more customized way. For example, the following comparator sorts strings by length, then alphabetically if lengths are equal, and always places null values last:

public class Main {
    public static void main(String[] args) {
        Set<String> names = new TreeSet<>(new LengthThenAlphabeticComparator());
        names.add("Bob");
        names.add(null);
        names.add("Alice");
        names.add("Eve");
        names.add("Dave");
        names.add("Dan");
        names.add(null);
        names.add("John");

        System.out.println(names); // [Bob, Dan, Eve, Dave, John, Alice, null]
    }
}

class LengthThenAlphabeticComparator implements Comparator<String> {
    @Override
    public int compare(String a, String b) {
        if (a == null && b == null) { return 0; }
        if (a == null) { return 1; }
        if (b == null) { return -1; }

        int lenCompare = Integer.compare(a.length(), b.length());
        return (lenCompare != 0) ? lenCompare : a.compareTo(b);
    }
}

A custom comparator gives you full control over how null elements should behave in your set, offering more flexibility than the built-in comparators likeComparator.nullsFirst() or Comparator.nullsLast().

TreeSet alternatives

While TreeSet offers sorted, unique, and searchable storage, there are cases where other collections may be more appropriate:

• If you need faster performance for basic operations without concern for order, consider using HashSet.

• If you require elements in insertion order, LinkedHashSet is a better choice.

• If you need random access by index, use a list like ArrayList.

• For thread-safe sorted sets, consider using Collections.synchronizedNavigableSet() or third-party concurrent collections like ConcurrentSkipListSet.

TreeSet is excellent for sorted sets, but not always the best for every scenario. So, you should always choose based on your particular use case.

Conclusion

The TreeSet class in Java is part of the java.util package and is a popular implementation of the Set interface. It is particularly useful when you need to store a collection of unique elements in a sorted order, with efficient search capabilities.

Below is an overview of its key characteristics:

• Stores only unique elements — duplicates are not allowed.

• Maintains elements in a sorted order (natural or defined by a custom comparator).

• Does not allow null elements with natural ordering.

• Offers $O(\log n)$ time complexity for basic operations thanks to its red-black tree structure.

• Not synchronized — requires external synchronization if used in multithreaded contexts.

• Does not support random access by index (unlike lists).

Because of these properties, TreeSet is an excellent choice when you need a searchable, sorted, and duplicate-free collection. However, if you require different ordering, support for nulls, or faster performance, alternatives like HashSet, LinkedHashSet, or ArrayList may be more suitable.