Java TreeSet

TreeSet<E> is the implementation of Set that keeps its elements sorted. It's backed by a red-black tree (the same balanced binary search tree that backs TreeMap underneath), so every operation — add, remove, contains, first, last, range queries — is O(log n). That's slower than HashSet's O(1), but you get something HashSet can't deliver at all: a sorted iterator, the smallest element on demand, and the ability to ask "every tag between a and m."

TreeSet implements the richer NavigableSet<E> interface (which extends SortedSet<E>), so all the range and neighbour queries are on the class itself, not buried in Collections helpers. If you haven't met the base contract yet, read the Set interface chapter first — everything there (no duplicates, add returns false on a repeat) still holds.

Two ways to define the order

A TreeSet needs some way to compare elements. There are two:

1. Natural ordering — the element type implements Comparable<E>. String, Integer, LocalDate, every wrapper, every enum, every record you write that implements Comparable. The no-arg constructor new TreeSet<>() uses this.
2. A Comparator<E> you supply — pass one to the constructor. The set uses your comparator for every comparison.

Set<String> caseInsensitive = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitive.add("Banana");
caseInsensitive.add("apple");
caseInsensitive.add("BANANA");   // equals "Banana" by this comparator → not added
System.out.println(caseInsensitive); // [apple, Banana]

The second example is important. TreeSet decides "equal" by compareTo returning 0, not by equals. Two strings the natural ordering says are different but a comparator says are equal will collapse to one element. That's almost always what you want — but it's a sharp edge if you didn't realise.

The NavigableSet API

A TreeSet exposes operations a plain Set can't:

TreeSet<Integer> t = new TreeSet<>(List.of(10, 20, 30, 40, 50));
t.first();          // 10  — smallest
t.last();           // 50  — largest
t.lower(30);        // 20  — strictly less than 30
t.floor(30);        // 30  — ≤ 30
t.higher(30);       // 40  — strictly greater than 30
t.ceiling(30);      // 30  — ≥ 30
t.pollFirst();      // 10, removes
t.pollLast();       // 50, removes
t.headSet(30);      // {10, 20}        — strictly less than 30
t.tailSet(30);      // {30, 40, 50}    — ≥ 30
t.subSet(20, 40);   // {20, 30}        — [20, 40)
t.descendingSet();  // a reverse-order view

These are the operations that justify the O(log n) cost: a HashSet can't do any of them at all without sorting the whole set first. If you need any of them, TreeSet is the right choice.

No nulls

A TreeSet cannot hold null because it would need to compare null with the other elements and compareTo(null) is a NullPointerException. The set throws on first insertion. If you need a sentinel, use a different value of the element type — Integer.MIN_VALUE, an empty String, or a dedicated marker in an enum.

Mutating elements is forbidden (same trap as HashSet)

TreeSet decides bucket placement at insert time by calling compareTo (or your Comparator). If you mutate an element after insertion in a way that changes the ordering, the tree's invariants break: contains searches the wrong subtree, remove can fail silently, iteration can return the same element twice or skip elements entirely.

The rule, restated: put effectively immutable elements in a TreeSet. Or, if your element does change, remove it before the change and re-add it after.

When to pick TreeSet

Decision flow:

• You need sorted iteration or range queries → TreeSet. The only choice.
• You need fast membership and order doesn't matter → HashSet. O(1) wins.
• You need fast membership and predictable iteration order → LinkedHashSet. Insertion order, not sorted.
• The element type is an enum → EnumSet. Faster than TreeSet and naturally ordered.

A useful pattern: do a heavy HashSet-based computation when speed matters, then new TreeSet<>(hashSet) once at the end if you need to present the result in order. Build fast, present sorted.

A worked example: leaderboard, comparator, and range queries

The program below uses TreeSet to maintain a leaderboard sorted by score (with a custom comparator), demonstrates the navigation methods, and shows how compareTo-based equality differs from equals-based equality.

What to take from the run:

• The integers came back in ascending order without any explicit sort. That sorted invariant is maintained on every add — the price is O(log n) per insert.
• The leaderboard used a two-stage comparator: descending by score, then ascending by name to keep tied players distinct. Always include a tie-breaker when scores can repeat or TreeSet will collapse them.
• The case-insensitive set rejected "JAVA" because, by the comparator, it equals "Java" — even though "JAVA".equals("Java") is false. Comparator equality, not equals equality.
• null threw — there's no sensible way to compare it with other elements.

What's next

Set is done; the other half of the framework is Map, the key-value abstraction. A Set can be thought of as a Map where you don't care about the value. The chapter on the Map interface is next, and the parallel structure with Set will be obvious once we start. TreeSet is in fact backed by a TreeMap, so the sorted-map navigation methods you saw here reappear there with keys instead of elements.

Practice