A TreeSet in Java is a sorted Set that keeps its unique elements in ascending order, either by their natural ordering or by a Comparator we pass to the constructor. It stores the elements in a red-black tree, so add(), remove() and contains() take O(log n) time, and it can answer questions such as “what is the next value after 42” in the same time.
We use TreeSet when the data must stay sorted while it changes, for example a leaderboard or a set of free appointment slots where we look up the closest match.
The following example shows the TreeSet operations covered in this article, with the result of each line as a comment.
TreeSet<Integer> scores = new TreeSet<>(List.of(70, 45, 90, 45, 82));
Set<Integer> sorted = scores; // [45, 70, 82, 90], duplicate dropped
Integer lowest = scores.first(); // 45
Integer highest = scores.last(); // 90
Integer atOrBelow = scores.floor(80); // 70
Integer atOrAbove = scores.ceiling(80); // 82
Integer above = scores.higher(90); // null, nothing above 90
SortedSet<Integer> under80 = scores.headSet(80); // [45, 70]
NavigableSet<Integer> desc = scores.descendingSet(); // [90, 82, 70, 45]Notice that higher(90) returns null instead of throwing an exception. We look at how the tree keeps the order, custom comparators, the duplicate trap with compareTo(), navigation and range methods with an appointment example, the Java 21 sequenced methods, null handling, and performance compared with HashSet.
1. Sorted Order in a TreeSet
Internally, TreeSet uses a TreeMap, which is a red-black tree. A red-black tree is a binary search tree that rebalances itself after every insert and delete, so its height never exceeds about 2 log2(n). Every value in a node’s left subtree is smaller than the node, and every value in its right subtree is larger.
To add, find or remove a value, the tree walks one path from the root and compares the value with each node on the way. For one million elements, that path has at most about 40 nodes, and in most trees close to 20. The same walk also finds the closest smaller or larger value, which a HashSet cannot do without scanning every element.
The class hierarchy reflects these abilities. The TreeSet class implements NavigableSet, which extends SortedSet, and since Java 21 SortedSet extends SequencedSet.
2. Natural Ordering and Custom Comparators
With the no-argument constructor, TreeSet sorts by natural ordering, which means the elements must implement Comparable. Classes such as String, Integer and LocalDate do, and so do enums. An element type without natural ordering fails with ClassCastException on the first add().
record Player(String name, int score) {}TreeSet<String> names = new TreeSet<>(List.of("raj", "Ana", "li"));
Set<String> natural = names; // [Ana, li, raj], uppercase sorts first
TreeSet<Player> broken = new TreeSet<>();
broken.add(new Player("ana", 50)); // ClassCastException, Player is not ComparableFor any other order, we pass a Comparator to the constructor. Lambdas and the factory methods of Comparator keep it short, so there is no reason to write a separate comparator class.
TreeSet<String> reversed = new TreeSet<>(Comparator.reverseOrder());
reversed.addAll(List.of("b", "c", "a"));
Set<String> zToA = reversed; // [c, b, a]
TreeSet<String> ignoreCase = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
ignoreCase.addAll(List.of("raj", "Ana", "li"));
Set<String> alpha = ignoreCase; // [Ana, li, raj]
TreeSet<Player> board = new TreeSet<>(Comparator.comparingInt(Player::score).reversed()
.thenComparing(Player::name));
board.addAll(List.of(new Player("ana", 50), new Player("raj", 80), new Player("li", 50)));
String leader = board.first().name(); // "raj"
String lastPlace = board.last().name(); // "li"The leaderboard sorts by score from high to low, and players with the same score sort by name. The Comparator with lambdas article shows more ways to chain comparators.
3. Duplicates Are Decided by compareTo(), Not equals()
A TreeSet never calls equals() or hashCode(). Two elements are duplicates when the comparator, or compareTo(), returns 0 for them. When the comparator looks at fewer fields than equals(), the set drops elements that we consider different, without any error or warning.
TreeSet<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length));
boolean addedCat = byLength.add("cat"); // true
boolean addedDog = byLength.add("dog"); // false, same length as cat
TreeSet<Player> byScore = new TreeSet<>(Comparator.comparingInt(Player::score));
byScore.add(new Player("ana", 50));
byScore.add(new Player("li", 50));
int players = byScore.size(); // 1, li was droppedThe comparator of a TreeSet must be consistent with equals(), which means it returns 0 only for elements that are equal, otherwise the set loses data. The fix is a tie-breaker with thenComparing() on the remaining fields, as in the leaderboard of section 2.
4. floor(), ceiling() and Other Lookups
The NavigableSet interface adds methods that find the closest element to a given value. They return null when no such element exists, so we wrap the result in an Optional or check it before use.
| Method | Returns | For {45, 70, 82, 90} |
|---|---|---|
| floor(80) | Greatest element less than or equal to the value | 70 |
| ceiling(80) | Smallest element greater than or equal to the value | 82 |
| lower(70) | Greatest element strictly less than the value | 45 |
| higher(70) | Smallest element strictly greater than the value | 82 |
| pollFirst() / pollLast() | Removes and returns the lowest or highest element, null if empty | 45 / 90 |
| first() / last() | Lowest or highest element, NoSuchElementException if empty | 45 / 90 |
A booking app is a good real case. A clinic has free appointment slots, and when a patient asks for 10:20, the app offers the first free slot at or after that time. Once the slot is booked, it leaves the set.
static Optional<LocalTime> book(TreeSet<LocalTime> free, LocalTime wanted) {
LocalTime slot = free.ceiling(wanted);
if (slot != null) {
free.remove(slot);
}
return Optional.ofNullable(slot);
}TreeSet<LocalTime> free = new TreeSet<>(List.of(
LocalTime.of(9, 0), LocalTime.of(10, 30), LocalTime.of(11, 0)));
Optional<LocalTime> booked = book(free, LocalTime.of(10, 20)); // Optional[10:30]
Optional<LocalTime> late = book(free, LocalTime.of(11, 30)); // Optional.empty
Set<LocalTime> remaining = free; // [09:00, 11:00]Each call takes O(log n) time, whether the clinic has 10 free slots or 10,000. With a sorted List, we would need a binary search plus an O(n) removal, and with a HashSet we would need to scan every slot.
5. Range Views With headSet(), tailSet() and subSet()
Range methods return a view of part of the set, not a copy. By default, the lower bound is inclusive and the upper bound is exclusive. The NavigableSet overloads with boolean flags let us choose both.
TreeSet<Integer> ages = new TreeSet<>(List.of(12, 18, 25, 33, 41, 67));
SortedSet<Integer> minors = ages.headSet(18); // [12]
SortedSet<Integer> adults = ages.tailSet(18); // [18, 25, 33, 41, 67]
SortedSet<Integer> twenties = ages.subSet(20, 30); // [25]
NavigableSet<Integer> upTo41 = ages.headSet(41, true); // [12, 18, 25, 33, 41]
NavigableSet<Integer> working = ages.subSet(18, true, 67, false); // [18, 25, 33, 41]Changes in either direction show up in the other, because the view reads the same tree. Adding a value outside the view’s range fails.
TreeSet<Integer> levels = new TreeSet<>(List.of(1, 5, 9));
SortedSet<Integer> low = levels.headSet(5);
levels.add(3);
SortedSet<Integer> lowNow = low; // [1, 3]
low.add(7); // IllegalArgumentException: key out of range6. TreeSet and Java 21 SequencedSet
Java 21 added sequenced collections, and TreeSet got the methods getFirst(), getLast(), removeFirst(), removeLast() and reversed(). They match first(), last(), pollFirst(), pollLast() and descendingSet(), except that removeFirst() and removeLast() throw NoSuchElementException on an empty set where the poll methods return null. The new methods work the same way on every sequenced collection, so a method that takes a SequencedSet accepts a TreeSet or a LinkedHashSet.
TreeSet<String> versions = new TreeSet<>(List.of("1.2", "1.10", "1.0"));
String oldest = versions.getFirst(); // "1.0"
String newest = versions.getLast(); // "1.2", string order, not numeric
SequencedSet<String> desc = versions.reversed(); // [1.2, 1.10, 1.0]
versions.addFirst("0.9"); // UnsupportedOperationExceptionThe methods addFirst() and addLast() throw UnsupportedOperationException, because the comparator decides the position of every element. Notice also that “1.10” sorts before “1.2” as text, so real version numbers need a comparator that compares the numeric parts.
7. Null Elements and Thread Safety
With natural ordering, TreeSet rejects null, because it cannot call compareTo() on it. A comparator built with Comparator.nullsFirst() or nullsLast() handles null and lets the set hold one.
TreeSet<String> plain = new TreeSet<>();
plain.add(null); // NullPointerException
TreeSet<String> nullable = new TreeSet<>(Comparator.nullsFirst(Comparator.naturalOrder()));
nullable.addAll(Arrays.asList("b", null, "a"));
String firstValue = nullable.first(); // null
Set<String> withNull = nullable; // [null, a, b]The TreeSet class is not synchronized, and its iterators are fail-fast. For a sorted set shared by many threads, we use ConcurrentSkipListSet, which has the same navigation methods, takes no global lock and never throws ConcurrentModificationException during iteration.
8. TreeSet vs HashSet Performance
A TreeSet pays for sorting on every change. For plain membership checks, a HashSet is faster, so we pick TreeSet only when we use the order.
| Operation | HashSet | TreeSet |
|---|---|---|
| add(), remove(), contains() | O(1) average | O(log n) guaranteed |
| Sorted iteration | Sort first, O(n log n) | O(n), already sorted |
| first(), last(), floor(), ceiling() | Scan, O(n) | O(log n) |
| Range views | Not available | O(log n) to create |
| Equality check | equals() and hashCode() | compareTo() or the comparator |
When we only need sorted output once, at the end, it is cheaper to collect into a HashSet and sort once with a stream. The Java Collections guide compares all Set types, and TreeMap offers the same features for key-value pairs.
9. TreeSet FAQs
Developers often search for these questions about Java TreeSet.
9.1. Does TreeSet allow duplicates?
No. When the comparator, or compareTo(), returns 0 for a new element and an existing one, add() returns false and keeps the existing element. This also drops elements that are not equal by equals() if the comparator ignores the fields that differ.
9.2. How do I sort a TreeSet in descending order?
We pass Comparator.reverseOrder() to the constructor, or we read an existing set through descendingSet() or the Java 21 reversed() view. Both views take constant time to create and do not copy the elements.
9.3. Is TreeSet faster than HashSet?
No, for add(), remove() and contains() a HashSet is faster, O(1) against O(log n). A TreeSet wins when we need sorted iteration or the element closest to a given value.
9.4. What is the difference between first() and getFirst() in TreeSet?
Both return the lowest element and throw NoSuchElementException on an empty set. The method first() comes from SortedSet and exists since Java 1.2, while getFirst() comes from SequencedCollection in Java 21 and works the same on lists, deques and sets.
10. Conclusion
A TreeSet keeps unique elements sorted in a red-black tree, with O(log n) time for changes and lookups. Its navigation methods, such as floor() and ceiling(), and its range views make it the right type for leaderboards, time slots and other data where we look for the nearest value.
We define the order with natural ordering or a lambda-based Comparator, and we make that comparator consistent with equals() so no element gets lost. For unsorted membership checks, HashSet stays faster, and for concurrent code, ConcurrentSkipListSet is the sorted alternative.
11. References
- TreeSet Javadoc (Java 25)
- NavigableSet Javadoc (Java 25)
- Comparable Javadoc, consistency with equals
Happy Learning !!
what is the initial capacity, load factor and grow factor for TreeSet?