TreeSet

A TreeSet is a set that keeps its elements sorted. Like every Set, it stores each element at most once. Unlike HashSet, it always iterates in order, and it can answer questions that depend on order: what is the smallest element, the largest, the next one after a given value, or all elements in a range. Internally it uses a self-balancing binary search tree (a red-black tree), so its main operations take O(log n) time.

Creating and Using a TreeSet

import java.util.TreeSet;

TreeSet<Integer> scores = new TreeSet<>();
scores.add(72);
scores.add(95);
scores.add(58);
scores.add(72);                     // duplicate: ignored

System.out.println(scores);         // [58, 72, 95]
System.out.println(scores.first()); // 58
System.out.println(scores.last());  // 95

Elements come out in ascending order regardless of the order they were added. Strings sort alphabetically, dates chronologically, and numbers numerically:

TreeSet<String> langs = new TreeSet<>(List.of("python", "java", "bash", "go"));
System.out.println(langs);          // [bash, go, java, python]

How Ordering Is Determined

A TreeSet needs to compare elements. It uses either:

1. The elements' natural ordering, if they implement Comparable (String, Integer, LocalDate, enums, and so on), or
2. A Comparator passed to the constructor.

TreeSet<String> byLength = new TreeSet<>(
        Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
byLength.addAll(List.of("docker", "c", "java", "bash"));
System.out.println(byLength);       // [c, bash, java, docker]

TreeSet<Integer> descending = new TreeSet<>(Comparator.reverseOrder());
descending.addAll(List.of(3, 1, 2));
System.out.println(descending);     // [3, 2, 1]

If the elements are not Comparable and no comparator is given, the first add throws ClassCastException.

Uniqueness comes from the comparison, not equals

This is the most important difference from HashSet. A TreeSet decides that two elements are duplicates when compareTo (or the comparator) returns 0. It never calls equals or hashCode.

TreeSet<String> words = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
words.add("java");
words.add("Java");                  // compares as equal to "java": not added
words.add("bash");
System.out.println(words);          // [bash, java]

The same pitfall appears with a comparator that compares only one field:

record Student(String name, int marks) { }

TreeSet<Student> ranked = new TreeSet<>(Comparator.comparingInt(Student::marks));
ranked.add(new Student("Ada", 90));
ranked.add(new Student("Linus", 90));   // same marks → treated as a duplicate and dropped!
System.out.println(ranked.size());       // 1

Add a tie-breaker so that only truly identical elements compare as equal:

TreeSet<Student> ranked = new TreeSet<>(
        Comparator.comparingInt(Student::marks).reversed().thenComparing(Student::name));

Ideally, an ordering should be consistent with equals: compare(a, b) == 0 exactly when a.equals(b).

Navigation Methods

TreeSet implements NavigableSet, which adds methods for finding elements relative to a value:

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

lower, floor, ceiling, and higher return null when no such element exists: n.floor(5) is null. first() and last() throw NoSuchElementException on an empty set, while pollFirst() and pollLast() return null.

These methods answer "nearest value" questions in O(log n) time, without scanning the whole collection: the next available appointment, the closest price point, the tax bracket for an income.

Range Views

A TreeSet can return a view of the elements within a range:

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

n.headSet(30);                  // [10, 20]          elements < 30
n.headSet(30, true);            // [10, 20, 30]      elements ≤ 30
n.tailSet(30);                  // [30, 40, 50]      elements ≥ 30
n.subSet(20, 40);               // [20, 30]          20 ≤ e < 40
n.subSet(20, true, 40, true);   // [20, 30, 40]      both ends inclusive
n.descendingSet();              // [50, 40, 30, 20, 10]

By default, the lower bound is inclusive and the upper bound is exclusive, matching the convention used throughout Java (substring, copyOfRange). The overloads with boolean flags control each end explicitly.

These are views, not copies: they reflect later changes to the original set, and changes through the view affect the original. Adding an element outside the view's range through the view throws IllegalArgumentException.

Performance

For one million elements, log₂ n is about 20, so a TreeSet lookup takes around 20 comparisons. That is slower than a hash lookup but still very fast. Choose TreeSet when you need ordering or nearest-value queries; otherwise HashSet is quicker.

Null Elements

A TreeSet using natural ordering cannot hold null, because comparing null throws NullPointerException. With a comparator such as Comparator.nullsFirst(...), null can be supported, but it is rarely a good idea.

Mutable Elements

As with HashSet, do not change an element's fields that affect its ordering while it is in the set. The tree would no longer be correctly ordered, and lookups and removals for that element could fail. Use immutable elements: String, wrapper types, LocalDate, records with immutable components.

Converting and Sorting with TreeSet

Passing a collection to the constructor removes duplicates and sorts in one step:

List<String> raw = List.of("delhi", "chennai", "mumbai", "chennai");
TreeSet<String> cities = new TreeSet<>(raw);       // [chennai, delhi, mumbai]
List<String> asList = new ArrayList<>(cities);     // back to a list, sorted and unique

If you only need sorting with duplicates kept, sort a list instead (list.sort(...)); a TreeSet would silently drop the duplicates.

Practical Example: Appointment Slots

A clinic offers 30-minute slots between 9:00 and 13:00. Some are already booked. The program finds the nearest free slot around a requested time, lists slots in time windows, and books the earliest one.

import java.time.LocalTime;
import java.util.NavigableSet;
import java.util.TreeSet;

public class Slots {
    public static void main(String[] args) {
        NavigableSet<LocalTime> free = new TreeSet<>();
        for (LocalTime t = LocalTime.of(9, 0); t.isBefore(LocalTime.of(13, 0)); t = t.plusMinutes(30)) {
            free.add(t);
        }
        free.remove(LocalTime.of(10, 0));      // already booked
        free.remove(LocalTime.of(10, 30));

        LocalTime requested = LocalTime.of(10, 15);
        LocalTime next = free.ceiling(requested);
        LocalTime previous = free.floor(requested);
        System.out.println("Requested " + requested + " -> next free " + next + ", previous free " + previous);

        System.out.println("Morning (before 11:00): " + free.headSet(LocalTime.of(11, 0)));
        System.out.println("11:00 to 12:00 incl.:  " + free.subSet(LocalTime.of(11, 0), true, LocalTime.of(12, 0), true));
        System.out.println("First / last: " + free.first() + " / " + free.last());

        LocalTime booked = free.pollFirst();
        System.out.println("Booked earliest: " + booked + ", remaining " + free.size());
        System.out.println("Latest first: " + free.descendingSet());
    }
}

Output:

Requested 10:15 -> next free 11:00, previous free 09:30
Morning (before 11:00): [09:00, 09:30]
11:00 to 12:00 incl.:  [11:00, 11:30, 12:00]
First / last: 09:00 / 12:30
Booked earliest: 09:00, remaining 5
Latest first: [12:30, 12:00, 11:30, 11:00, 09:30]

LocalTime implements Comparable, so the set keeps slots in chronological order automatically. ceiling and floor find the free slots on either side of 10:15, skipping the booked 10:00 and 10:30 slots, without any loop. headSet and subSet return the slots in a time window as live views. pollFirst removes and returns the earliest slot in one step, which is exactly the "book the next available appointment" operation. The variable is declared as NavigableSet, the interface that defines all of these order-aware methods.