Java TreeSet

The Java TreeSet Class

The TreeSet class is an implementation of the Set interface that uses a tree structure (specifically, a Red-Black Tree) for storage.

The most important feature of a TreeSet is that it stores its elements in a sorted order.

Key Characteristics of TreeSet

• No Duplicates: Like all Set implementations, it does not allow duplicate elements.
• Sorted Order: It automatically sorts the elements. By default, it uses the "natural ordering" of the elements. For example, integers are sorted numerically, and strings are sorted alphabetically. You can also provide a custom sorting logic using a Comparator.
• No null Elements: TreeSet does not allow null elements, as it cannot compare null to other elements for sorting.
• Slower Performance: Because it has to maintain the sorted order, its performance for add, remove, and contains operations is O(log n), which is slower than HashSet's O(1).
• NavigableSet: TreeSet implements the NavigableSet interface, which provides useful methods for finding elements relative to others in the sorted set (e.g., floor(), ceiling(), higher(), lower()).

How TreeSet Works

A TreeSet is backed by a TreeMap. When you add an element, it is placed into the underlying tree structure based on its comparison to the other elements. This comparison is done using either the element's compareTo() method (if the class implements the Comparable interface) or a Comparator provided to the TreeSet's constructor.

This tree structure is always kept balanced, which guarantees the O(log n) performance for operations.

When to Use TreeSet

TreeSet is the perfect choice when you need a collection that:

1. Guarantees uniqueness of elements.
2. Requires the elements to be always stored in a sorted order.

If you don't need sorting, HashSet or LinkedHashSet will provide better performance.

TreeSet Example

Here is an example demonstrating the sorting behavior of a TreeSet.

import java.util.TreeSet;

public class Main {
  public static void main(String[] args) {
    // Create a TreeSet of Integers
    TreeSet numbers = new TreeSet<>();
    // Add items
    numbers.add(50);
    numbers.add(10);
    numbers.add(80);
    numbers.add(10); // This will be ignored
    // The elements are automatically sorted
    System.out.println("Sorted TreeSet: " + numbers);
    // NavigableSet methods
    System.out.println("First element: " + numbers.first());
    System.out.println("Last element: " + numbers.last());
    System.out.println("Element higher than 50: " + numbers.higher(50));
    System.out.println("Element lower than 50: " + numbers.lower(50));
  }
}

Advanced: Custom Sorting with Comparators (Java 8+)

By default, TreeSet relies on the natural ordering of elements (e.g., alphabetical for Strings). If you want to sort elements differently (like by string length, or in reverse order), you can pass a Comparator into the TreeSet constructor. With Java 8 lambda expressions, this is incredibly concise.

import java.util.TreeSet;

public class Main {
  public static void main(String[] args) {
    // We refine the comparator to fall back to alphabetical order if lengths are equal!
    TreeSet<String> safeWords = new TreeSet<>((s1, s2) -> {
        int lenCompare = Integer.compare(s1.length(), s2.length());
        return lenCompare != 0 ? lenCompare : s1.compareTo(s2);
    });
    safeWords.add("Elephant");
    safeWords.add("Cat");
    safeWords.add("Dog");
    safeWords.add("Hippopotamus");
    System.out.println("Sorted by length: " + safeWords);
  }
}

Advanced: Subset Operations

Because TreeSet implements NavigableSet and SortedSet, it allows you to extract portions of the set efficiently.

import java.util.TreeSet;
import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    TreeSet<Integer> numbers = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50, 60, 70));
    // Get numbers strictly less than 40
    System.out.println("HeadSet (< 40): " + numbers.headSet(40));
    // Get numbers greater than or equal to 40
    System.out.println("TailSet (>= 40): " + numbers.tailSet(40));
    // Get numbers between 20 (inclusive) and 60 (exclusive)
    System.out.println("SubSet (20 to 59): " + numbers.subSet(20, 60));
  }
}