The Collections Framework

TreeSet & Sorted Sets

15 min Lesson 5 of 14

TreeSet & Sorted Sets

A HashSet gives you fast membership tests but makes no promises about order. Sometimes you need both uniqueness and a predictable sorted order — that is exactly what TreeSet provides. Understanding when and why to reach for TreeSet instead of HashSet is an important step in writing expressive, efficient Java code.

What TreeSet is Under the Hood

TreeSet<E> is a NavigableSet backed by a red-black tree. Every insertion and removal is O(log n) instead of the near-O(1) of a hash-based set. The trade-off is that iteration always visits elements in ascending sorted order, and a rich family of navigation methods becomes available.

The SortedSet hierarchy: TreeSet implements NavigableSet, which extends SortedSet, which extends Set. When you only need sorted iteration, type your variable as SortedSet. When you need navigation methods (floor, ceiling, etc.), use NavigableSet.

Natural Ordering with Comparable

When you construct a TreeSet without passing a comparator, it uses natural ordering — the ordering defined by the elements' own Comparable<T> implementation. All Java wrapper types (Integer, String, LocalDate, …) already implement Comparable, so this works out of the box:

import java.util.TreeSet;

TreeSet<String> languages = new TreeSet<>();
languages.add("Python");
languages.add("Java");
languages.add("C++");
languages.add("Rust");
languages.add("Java");   // duplicate — silently ignored

System.out.println(languages);
// Output: [C++, Java, Python, Rust]   (alphabetical, no duplicates)

For your own classes you implement Comparable<T> by overriding compareTo. The contract: return a negative number when this is less-than the argument, zero when equal, and a positive number when greater.

public class Student implements Comparable<Student> {
    private final String name;
    private final double gpa;

    public Student(String name, double gpa) {
        this.name = name;
        this.gpa  = gpa;
    }

    @Override
    public int compareTo(Student other) {
        // Primary sort: GPA descending (higher GPA first)
        int cmp = Double.compare(other.gpa, this.gpa);
        // Secondary sort: name ascending to break ties
        return (cmp != 0) ? cmp : this.name.compareTo(other.name);
    }

    @Override
    public String toString() { return name + "(" + gpa + ")"; }
}

// Usage
TreeSet<Student> ranked = new TreeSet<>();
ranked.add(new Student("Alice",  3.9));
ranked.add(new Student("Bob",    3.7));
ranked.add(new Student("Carol",  3.9));

System.out.println(ranked);
// [Alice(3.9), Carol(3.9), Bob(3.7)]

compareTo must be consistent with equals. If two objects compare as zero they should also be equals() to each other — otherwise a TreeSet will treat them as duplicates while a HashSet would not, leading to confusing bugs when you switch implementations.

NavigableSet Operations

TreeSet exposes powerful navigation methods that have no equivalent on HashSet:

first() / last() — smallest / largest element.
floor(e) — greatest element ≤ e, or null.
ceiling(e) — smallest element ≥ e, or null.
lower(e) — greatest element strictly less than e.
higher(e) — smallest element strictly greater than e.
headSet(to) / tailSet(from) — views of elements before / from a value.
subSet(from, to) — a live view of the range [from, to).
pollFirst() / pollLast() — remove and return the smallest / largest.

TreeSet<Integer> scores = new TreeSet<>(
    java.util.List.of(55, 72, 88, 91, 64, 78, 91, 99)
);
// {55, 64, 72, 78, 88, 91, 99}  (sorted, no duplicate 91)

System.out.println(scores.first());         // 55
System.out.println(scores.last());          // 99
System.out.println(scores.floor(80));       // 78  (≤ 80)
System.out.println(scores.ceiling(80));     // 88  (≥ 80)
System.out.println(scores.lower(78));       // 72  (strictly < 78)
System.out.println(scores.higher(78));      // 88  (strictly > 78)

// Live subset view — changes to the subset reflect in the original
var passing = scores.tailSet(60);           // [64, 72, 78, 88, 91, 99]
System.out.println(passing);
passing.remove(64);                         // also removes 64 from scores
System.out.println(scores);                 // [55, 72, 78, 88, 91, 99]

Subset views are live, not copies. headSet, tailSet, and subSet return backed views. Mutations through the view propagate to the original set and vice versa — useful for range deletions or range iteration without copying.

Descending Order

Need to iterate from highest to lowest without writing a custom comparator? Call descendingSet():

TreeSet<Integer> asc = new TreeSet<>(java.util.List.of(3, 1, 4, 1, 5, 9));
// asc: [1, 3, 4, 5, 9]

var desc = asc.descendingSet();             // backed view, not a copy
System.out.println(desc);                   // [9, 5, 4, 3, 1]

When to Choose TreeSet over HashSet

You need to iterate elements in sorted order.
You need range queries (all elements between X and Y).
You need the minimum or maximum element quickly.
Your elements implement Comparable (or you supply a Comparator).

If none of these apply, stick with HashSet — its O(1) operations beat TreeSet's O(log n) for pure membership tests at large scale.

Summary

TreeSet stores unique elements in sorted order using a red-black tree. Natural ordering relies on Comparable; supply a Comparator when you need a different order or when the element type is not Comparable. The NavigableSet API — floor, ceiling, headSet, subSet, and friends — makes range-based lookups expressive and efficient. Next we will look at the map equivalent of TreeSet: TreeMap and LinkedHashMap.