SortedSet, NavigableSet and TreeSet in Java

A grade report keeps exam scores in a TreeSet: [72, 80, 85, 90, 97]. The “B” band is 80 to 90, so the code calls scores.subSet(80, 90) — and gets [80, 85]. The student who scored exactly 90 silently disappears from the report: the upper bound of a SortedSet range is always exclusive. The NavigableSet overload scores.subSet(80, true, 90, true) returns [80, 85, 90].

SortedSet (java.util.SortedSet<E>) is the interface of a sorted set: unique elements kept in ascending order, either by their natural ordering (Comparable) or by a Comparator. NavigableSet extends it with nearest-element lookups — ceiling(), floor(), higher(), lower() — and ranges with explicit bounds. TreeSet is the main implementation of both interfaces; it is built on a red-black tree, so add(), remove() and contains() run in O(log n).

SortedSet in Java: first, last, headSet, subSet, tailSet

SortedSet in Java is a Set that always keeps its elements sorted. It adds six methods: first() and last() return the smallest and largest element, headSet(), subSet() and tailSet() return ranges, and comparator() returns the sorting rule. The order comes from the elements’ Comparable implementation or from a Comparator passed to the constructor.

A Java SortedSet example with first(), last(), subSet(), headSet() and tailSet():

import java.util.SortedSet;
import java.util.TreeSet;

public class SortedSetExample {
    public static void main(String[] args) {
        SortedSet<String> cities = new TreeSet<>();

        cities.add("Paris");
        cities.add("Berlin");
        cities.add("London");
        cities.add("Madrid");
        cities.add("Paris");

        System.out.println(cities);
        System.out.println("SubSet: " + cities.subSet("Berlin", "Madrid"));
        System.out.println("HeadSet: " + cities.headSet("London"));
        System.out.println("TailSet: " + cities.tailSet("London"));
        System.out.println("First: " + cities.first());
        System.out.println("Last: " + cities.last());
        System.out.println("Comparator: " + cities.comparator());
    }
}

Output:

[Berlin, London, Madrid, Paris]
SubSet: [Berlin, London]
HeadSet: [Berlin]
TailSet: [London, Madrid, Paris]
First: Berlin
Last: Paris
Comparator: null

The second “Paris” was not added — it is still a set. “Madrid” is missing from subSet("Berlin", "Madrid") and “London” from headSet("London"): in a SortedSet the lower bound of a range is included and the upper bound is excluded. comparator() returns null because the set uses the natural ordering of String. That ordering compares character codes, so a lowercase “amsterdam” would land after “Paris” — see How compareTo compares strings.

NavigableSet in Java: ceiling, floor, higher, lower

NavigableSet in Java is an interface that extends SortedSet with navigation methods: find the element closest to a given value, remove the first or last element, iterate in reverse order and take a range with explicitly included or excluded bounds. It was added in Java 6 and is implemented by TreeSet and ConcurrentSkipListSet.

The lookup methods never throw when nothing matches — they return null. The two pairs differ only in strictness: ceiling() and floor() accept an equal element, higher() and lower() do not.

What does this code print? One set, four methods, four different answers:

import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;

public class NearestExample {
    public static void main(String[] args) {
        NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30));

        System.out.println(set.ceiling(20)); // 20 - an equal element qualifies
        System.out.println(set.higher(20));  // 30 - only strictly greater
        System.out.println(set.floor(20));   // 20
        System.out.println(set.lower(20));   // 10
        System.out.println(set.ceiling(35)); // null - nothing is 35 or greater
        System.out.println(set.floor(5));    // null - nothing is 5 or less
    }
}

Output:

20
30
20
10
null
null

A practical NavigableSet example is a bus timetable stored as HHMM numbers. The same two questions can be answered with SortedSet methods and with NavigableSet methods:

import java.util.NavigableSet;
import java.util.SortedSet;
import java.util.TreeSet;

public class BusTimetable {
    public static void main(String[] args) {
        NavigableSet<Integer> departures = new TreeSet<>();
        departures.add(1205);
        departures.add(1505);
        departures.add(1545);
        departures.add(1830);
        departures.add(2010);
        departures.add(2100);

        // SortedSet methods: headSet() and tailSet()
        System.out.println("SortedSet");
        SortedSet<Integer> before = departures.headSet(1600);
        System.out.println("Last bus before 16:00: " + before.last());
        SortedSet<Integer> after = departures.tailSet(2000);
        System.out.println("First bus after 20:00: " + after.first());
        System.out.println();

        // NavigableSet methods: lower() and higher()
        System.out.println("NavigableSet");
        System.out.println("Last bus before 16:00: " + departures.lower(1600));
        System.out.println("First bus after 20:00: " + departures.higher(2000));
    }
}

Output:

SortedSet
Last bus before 16:00: 1545
First bus after 20:00: 2010

NavigableSet
Last bus before 16:00: 1545
First bus after 20:00: 2010

The results match, but lower() and higher() are shorter and safer. If no bus leaves before 16:00, departures.lower(1600) returns null, while departures.headSet(1600).last() throws NoSuchElementException because the subset is empty.

headSet, tailSet and subSet with inclusive flags

The SortedSet range methods work with a half-open interval: the lower bound is included, the upper bound is not. NavigableSet adds overloads of the same methods with a boolean inclusive parameter, so you decide for each bound whether it is included. Both versions return a view of the original set, not a copy.

import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;

public class RangeExample {
    public static void main(String[] args) {
        NavigableSet<Integer> scores = new TreeSet<>(List.of(72, 80, 85, 90, 97));

        System.out.println(scores.headSet(85));                 // [72, 80]
        System.out.println(scores.headSet(85, true));           // [72, 80, 85]
        System.out.println(scores.tailSet(85));                 // [85, 90, 97]
        System.out.println(scores.tailSet(85, false));          // [90, 97]
        System.out.println(scores.subSet(80, 90));              // [80, 85]
        System.out.println(scores.subSet(80, true, 90, true));  // [80, 85, 90]
        System.out.println(scores.subSet(80, false, 90, true)); // [85, 90]
        System.out.println(scores.subSet(90, 80));              // IllegalArgumentException
    }
}

Output:

[72, 80]
[72, 80, 85]
[85, 90, 97]
[90, 97]
[80, 85]
[80, 85, 90]
[85, 90]
Exception in thread "main" java.lang.IllegalArgumentException: fromKey > toKey

The bounds do not have to be elements of the set: scores.subSet(75, 95) returns [80, 85, 90]. The versions without flags are shorthand for headSet(toElement, false), tailSet(fromElement, true) and subSet(fromElement, true, toElement, false).

Subsets are views, not copies

headSet(), tailSet(), subSet() and descendingSet() do not copy elements: they return a view backed by the original set (a backed collection). Changes are visible both ways — an element added to the original set appears in the view, and an element removed through the view disappears from the original. A value outside the view’s range cannot be added through it.

import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;

public class BackedSetExample {
    public static void main(String[] args) {
        TreeSet<String> fruits = new TreeSet<>(List.of("apple", "banana", "cherry", "date", "fig"));
        NavigableSet<String> upToCherry = fruits.headSet("cherry", true);
        System.out.println(upToCherry);   // [apple, banana, cherry]

        fruits.add("blueberry");
        System.out.println(upToCherry);   // [apple, banana, blueberry, cherry]

        upToCherry.remove("apple");
        System.out.println(fruits);       // [banana, blueberry, cherry, date, fig]

        upToCherry.add("grape");          // "grape" is after "cherry"
    }
}

Output:

[apple, banana, cherry]
[apple, banana, blueberry, cherry]
[banana, blueberry, cherry, date, fig]
Exception in thread "main" java.lang.IllegalArgumentException: key out of range

If you need an independent copy of a range, wrap the view: new TreeSet<>(fruits.headSet("cherry", true)). The same view mechanism is behind subMap() of TreeMap and behind Arrays.asList().

pollFirst, pollLast, descendingSet and the TreeSet iterator

pollFirst() and pollLast() return the smallest and largest element and remove it at once; for an empty set they return null. descendingSet() returns a reverse-order view, and descendingIterator() walks from the largest element to the smallest. The regular iterator() of a TreeSet always goes in ascending order.

import java.util.Iterator;
import java.util.List;
import java.util.TreeSet;

public class PollDescendingExample {
    public static void main(String[] args) {
        TreeSet<String> steps = new TreeSet<>(List.of("deploy", "build", "test", "review"));

        System.out.println(steps.descendingSet());       // [test, review, deploy, build]

        Iterator<String> it = steps.descendingIterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");           // test review deploy build
        }
        System.out.println();

        System.out.println(steps.pollFirst());           // build
        System.out.println(steps.pollLast());            // test
        System.out.println(steps);                       // [deploy, review]

        TreeSet<String> empty = new TreeSet<>();
        System.out.println(empty.pollFirst());           // null
        System.out.println(empty.first());               // NoSuchElementException
    }
}

Output:

[test, review, deploy, build]
test review deploy build
build
test
[deploy, review]
null
Exception in thread "main" java.util.NoSuchElementException

A while ((x = set.pollFirst()) != null) loop processes elements in ascending order and empties the set at the same time. On Java 21, reversed() on a TreeSet returns the same kind of view as descendingSet(). The TreeSet iterator is fail-fast: if the set is modified during iteration other than through the iterator itself, the next call to next() throws ConcurrentModificationException.

What is TreeSet in Java: internals and constructors

TreeSet in Java is a class that implements NavigableSet (and therefore SortedSet and Set). Internally it stores its elements as keys of a TreeMap, a red-black tree, so add(), remove() and contains() take O(log n). That is slower than the O(1) on average of a HashSet, but much faster than the O(n) linear search in a list (see Big O notation).

The quickest way to get unique, sorted values from a list is to pass it to the constructor:

List<String> tags = List.of("sql", "java", "git", "java");
System.out.println(new TreeSet<>(tags)); // Output: [git, java, sql]

Duplicates are dropped and the rest are sorted — unlike a LinkedHashSet, which would keep the insertion order [sql, java, git]. The order is fixed when the set is created and never changes afterwards. TreeSet constructors:

Which of the last two constructors runs is decided by the compiler from the declared type of the variable, not from the actual object:

import java.util.Collection;
import java.util.Comparator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSetConstructorExample {
    public static void main(String[] args) {
        SortedSet<String> desc = new TreeSet<>(Comparator.reverseOrder());
        desc.addAll(List.of("alpha", "beta", "gamma"));

        System.out.println(new TreeSet<>(desc));          // [gamma, beta, alpha]

        Collection<String> asCollection = desc;
        System.out.println(new TreeSet<>(asCollection));  // [alpha, beta, gamma]
    }
}

Output:

[gamma, beta, alpha]
[alpha, beta, gamma]

The first call picks TreeSet(SortedSet), and the copy keeps the reverse order. In the second call the same object is declared as Collection, so TreeSet(Collection) runs and the copy is silently re-sorted in ascending order. All constructors and methods are listed in the TreeSet Javadoc.

SortedSet vs NavigableSet vs TreeSet: which to use

SortedSet and NavigableSet are interfaces and TreeSet is a class that implements them, so “SortedSet vs TreeSet” is really a question of which type to declare a variable with. Declare NavigableSet if you need ceiling(), floor() or inclusive range flags, and SortedSet if first(), last() and subSet() are enough. The implementation goes after new.

If you do not need sorting, use HashSet or LinkedHashSet — they are compared in LinkedHashSet vs HashSet. How a sorted collection differs from an ordered one is explained in Ordered vs sorted collections. For key–value pairs the counterparts are NavigableMap and TreeMap, and the general table for choosing a collection is in Choosing an implementation.

Common mistakes with TreeSet

Most TreeSet bugs come from range bounds, empty sets and forgetting that subsets are views rather than copies. The table lists the typical slips, what actually happens and how to write the code correctly.