Skip to content
Java collections 7 min read

TreeSet

TreeSet<E> is Java’s go-to implementation when you need a Set that keeps its elements automatically sorted. Every add, remove, and lookup runs in O(log n) time — a small price to pay for always having your data in order.

What is TreeSet?

TreeSet<E> lives in java.util and implements NavigableSet<E>, which itself extends SortedSet<E> and then Set<E>. Under the hood it is backed by a TreeMap, where each element you add becomes a key in that map.

Key characteristics at a glance:

FeatureDetail
DuplicatesNot allowed
Null elementsNot permitted (throws NullPointerException)
OrderSorted — natural ordering or a custom Comparator
Thread safetyNot synchronized
Time complexityO(log n) for add / remove / contains

Note: The “natural ordering” of a type is defined by its Comparable implementation. For String that is lexicographic order; for Integer it is numeric order. See Comparable for the full picture.

Creating a TreeSet

import java.util.TreeSet;

public class CreateTreeSet {
    public static void main(String[] args) {
        TreeSet<Integer> numbers = new TreeSet<>();

        numbers.add(42);
        numbers.add(7);
        numbers.add(19);
        numbers.add(3);
        numbers.add(7);  // duplicate — silently ignored

        System.out.println(numbers);       // sorted automatically
        System.out.println("Size: " + numbers.size());
    }
}

Output:

[3, 7, 19, 42]
Size: 4

The elements come out in ascending order no matter what order you inserted them.

TreeSet with Strings

import java.util.TreeSet;

public class StringTreeSet {
    public static void main(String[] args) {
        TreeSet<String> cities = new TreeSet<>();
        cities.add("Paris");
        cities.add("Tokyo");
        cities.add("Amsterdam");
        cities.add("Berlin");

        System.out.println(cities);
    }
}

Output:

[Amsterdam, Berlin, Paris, Tokyo]

Strings are sorted lexicographically (dictionary order), which is case-sensitive — uppercase letters come before lowercase in Unicode.

Custom Ordering with a Comparator

When natural ordering does not suit you, pass a Comparator to the constructor.

import java.util.Comparator;
import java.util.TreeSet;

public class ReverseTreeSet {
    public static void main(String[] args) {
        // Descending order using Comparator.reverseOrder()
        TreeSet<Integer> desc = new TreeSet<>(Comparator.reverseOrder());
        desc.add(10);
        desc.add(5);
        desc.add(30);
        desc.add(1);

        System.out.println(desc);
    }
}

Output:

[30, 10, 5, 1]

Tip: Comparator.reverseOrder() (Java 8+) is a concise built-in for descending order. For complex rules, write your own lambda or Comparator chain.

TreeSet with Custom Objects

For your own classes, either implement Comparable or supply a Comparator. If you do neither, adding the second element throws ClassCastException.

import java.util.TreeSet;

public class CustomObjectDemo {
    record Student(String name, int grade) implements Comparable<Student> {
        @Override
        public int compareTo(Student other) {
            // Primary: ascending grade; secondary: name
            int cmp = Integer.compare(this.grade, other.grade);
            return cmp != 0 ? cmp : this.name.compareTo(other.name);
        }
    }

    public static void main(String[] args) {
        TreeSet<Student> roster = new TreeSet<>();
        roster.add(new Student("Zara",  90));
        roster.add(new Student("Alice", 85));
        roster.add(new Student("Bob",   90));

        for (Student s : roster) {
            System.out.println(s.name() + " — " + s.grade());
        }
    }
}

Output:

Alice — 85
Bob — 90
Zara — 90

Warning: TreeSet uses the compareTo (or Comparator) result to decide whether two objects are equal for the purposes of the set. If your comparator returns 0 for two objects that are logically different, only one will be stored. Make sure your comparison is consistent with equals.

TreeSet implements NavigableSet, giving you a rich navigation API on top of the standard Set methods.

Boundary Retrieval

import java.util.TreeSet;

public class NavigateDemo {
    public static void main(String[] args) {
        TreeSet<Integer> ts = new TreeSet<>(java.util.Arrays.asList(10, 20, 30, 40, 50));

        System.out.println("first():    " + ts.first());    // 10
        System.out.println("last():     " + ts.last());     // 50
        System.out.println("floor(25):  " + ts.floor(25));  // 20  (≤ 25)
        System.out.println("ceiling(25):" + ts.ceiling(25));// 30  (≥ 25)
        System.out.println("lower(30):  " + ts.lower(30));  // 20  (strictly < 30)
        System.out.println("higher(30): " + ts.higher(30)); // 40  (strictly > 30)
    }
}

Output:

first():    10
last():     50
floor(25):  20
ceiling(25):30
lower(30):  20
higher(30): 40

Polling (Retrieving and Removing)

import java.util.TreeSet;

public class PollDemo {
    public static void main(String[] args) {
        TreeSet<Integer> ts = new TreeSet<>(java.util.Arrays.asList(5, 15, 25, 35));

        System.out.println("pollFirst(): " + ts.pollFirst()); // 5  (removed)
        System.out.println("pollLast():  " + ts.pollLast());  // 35 (removed)
        System.out.println("Remaining:   " + ts);            // [15, 25]
    }
}

Output:

pollFirst(): 5
pollLast():  35
Remaining:   [15, 25]

Sub-Sets and Views

TreeSet can return live views (backed by the same data) of a portion of the set.

import java.util.TreeSet;

public class SubSetDemo {
    public static void main(String[] args) {
        TreeSet<Integer> ts = new TreeSet<>(java.util.Arrays.asList(10, 20, 30, 40, 50, 60));

        // headSet: elements strictly less than 40
        System.out.println("headSet(40):         " + ts.headSet(40));

        // tailSet: elements >= 30
        System.out.println("tailSet(30):         " + ts.tailSet(30));

        // subSet: elements from 20 (inclusive) to 50 (exclusive)
        System.out.println("subSet(20, 50):       " + ts.subSet(20, 50));

        // subSet with explicit inclusive/exclusive flags (Java 6+)
        System.out.println("subSet(20,true,50,true): " + ts.subSet(20, true, 50, true));
    }
}

Output:

headSet(40):         [10, 20, 30]
tailSet(30):         [30, 40, 50, 60]
subSet(20, 50):       [20, 30, 40]
subSet(20,true,50,true): [20, 30, 40, 50]

Note: The sub-set views are live: changes to the view are reflected in the original TreeSet and vice versa. Modifying the backing set through elements outside the sub-set’s range throws IllegalArgumentException.

Descending View

import java.util.TreeSet;

public class DescendingDemo {
    public static void main(String[] args) {
        TreeSet<String> ts = new TreeSet<>(java.util.Arrays.asList("Mango", "Apple", "Cherry"));

        System.out.println("Ascending:  " + ts);
        System.out.println("Descending: " + ts.descendingSet());
    }
}

Output:

Ascending:  [Apple, Cherry, Mango]
Descending: [Mango, Cherry, Apple]

Iterating a TreeSet

Use a for-each loop for simple traversal, or an Iterator when you need to remove elements during iteration.

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

public class IterateDemo {
    public static void main(String[] args) {
        TreeSet<String> languages = new TreeSet<>(
            java.util.Arrays.asList("Java", "Rust", "Go", "Python"));

        // Forward iteration (sorted order)
        for (String lang : languages) {
            System.out.print(lang + " ");
        }
        System.out.println();

        // Reverse iteration
        Iterator<String> desc = languages.descendingIterator();
        while (desc.hasNext()) {
            System.out.print(desc.next() + " ");
        }
    }
}

Output:

Go Java Python Rust 
Rust Python Java Go

Under the Hood

Red-Black Tree

TreeSet is backed by a TreeMap, which stores entries in a self-balancing red-black tree. A red-black tree is a binary search tree with an extra colour bit per node and four balancing rules that guarantee the tree’s height stays within O(log n). This bound applies regardless of insertion order — unlike a plain binary search tree which can degrade to a linked list.

When you call add(e):

  1. The element is compared with the root using compareTo (or the Comparator).
  2. The comparison steers the traversal left (smaller) or right (larger) until the right spot is found.
  3. A new node is inserted and the tree is rebalanced if needed (rotations and colour flips — at most O(log n) work).

Why Not HashSet?

HashSet gives O(1) average time but provides no ordering guarantees. If you need to find “the smallest element greater than X” or iterate in sorted order, the O(log n) cost of TreeSet buys you a powerful and always-sorted data structure.

Memory Layout

Each TreeMap.Entry node stores: the key, the value (a constant PRESENT object for TreeSet), references to its left child, right child, parent, and a colour flag. This adds roughly 48 bytes per entry on a 64-bit JVM — more than a HashSet bucket entry. For very large collections that only need uniqueness without ordering, HashSet is the lighter choice.

TreeSet vs HashSet vs LinkedHashSet

HashSetLinkedHashSetTreeSet
OrderNoneInsertion orderSorted (natural or Comparator)
PerformanceO(1) avgO(1) avgO(log n)
Null allowedYes (one)Yes (one)No
Navigation APINoNoYes (floor, ceiling, …)
Backed byHashMapLinkedHashMapTreeMap
Use whenJust uniquenessUnique + insertion orderUnique + sorted + navigation

Common Pitfalls

  • Null elements — adding null always throws NullPointerException, even as the first element.
  • Inconsistent comparator — if your Comparator returns 0 for objects that are logically different, one of them will silently disappear from the set.
  • Mutating elements — if you change a field that your Comparator uses after the element is inserted, the tree’s ordering invariant breaks. The element may become unfindable. Treat TreeSet elements as effectively immutable with respect to the comparison key.
  • Thread safety — TreeSet is not synchronized. Wrap it with Collections.synchronizedSortedSet() when shared across threads.
import java.util.Collections;
import java.util.SortedSet;
import java.util.TreeSet;

SortedSet<String> safe = Collections.synchronizedSortedSet(new TreeSet<>());
  • Set Interface — the contract that TreeSet, HashSet, and LinkedHashSet all fulfill
  • HashSet — the fastest unordered Set backed by a HashMap
  • TreeMap — the sorted map that powers TreeSet internally
  • Comparable — how to define natural ordering for your own classes
  • Comparator — how to supply custom ordering rules to TreeSet
  • Comparable vs Comparator — when to use each approach
Last updated June 13, 2026
Was this helpful?