JavaData StructuresIntermediate

TreeSet

A Red-Black tree based implementation of the NavigableSet interface, providing unique, sorted elements and guaranteed log(n) time complexity for basic operations.

Review the syntaxStudy the examplesOpen the coding app
new TreeSet<E>()
new TreeSet<E>(Comparator<? super E> comparator)
Open Coding Reference

This static page keeps the syntax and examples indexed for search, while the coding app handles interactive exploration and saved references.

What it does

Overview

A Red-Black tree based implementation of the NavigableSet interface, providing unique, sorted elements and guaranteed log(n) time complexity for basic operations.

A `TreeSet` in Java is a sorted set implementation that stores unique elements in ascending order, either according to their natural ordering or by a `Comparator` provided at set creation time. It is backed by a `TreeMap`, where each element added to the `TreeSet` acts as a key in the internal `TreeMap`, and a dummy `Object` is used as the value. This structure guarantees O(log n) time complexity for `add()`, `contains()`, and `remove()` operations, making it highly efficient for scenarios requiring sorted, unique data. `TreeSet` is particularly useful for maintaining sorted lists of unique items, performing range queries, or finding the smallest/largest elements. Like `TreeMap`, it does not allow `null` elements (as they cannot be naturally ordered or compared by a `Comparator`). `TreeSet` also offers additional methods from the `NavigableSet` interface, such as `first()`, `last()`, `floor()`, `ceiling()`, which leverage its sorted nature. It is not thread-safe; for concurrent access, `ConcurrentSkipListSet` or `Collections.synchronizedSortedSet()` should be used. When order and uniqueness are paramount, `TreeSet` is the go-to choice over `HashSet`.

Quick reference

Syntax

new TreeSet<E>()
new TreeSet<E>(Comparator<? super E> comparator)

Inputs

Parameters

comparator (optional)Comparator<? super E> · The comparator that will be used to order this set. If null, the natural ordering of the elements will be used.

See it in practice

Examples

1

Basic TreeSet with natural ordering

import java.util.TreeSet;

TreeSet<String> uniqueWords = new TreeSet<>();
uniqueWords.add("apple");
uniqueWords.add("banana");
uniqueWords.add("orange");
uniqueWords.add("apple"); // Duplicate, won't be added

System.out.println("Unique words (sorted alphabetically): " + uniqueWords);
Output:
Unique words (sorted alphabetically): [apple, banana, orange]

Elements are automatically sorted by their natural (alphabetical) order, and duplicates are not added.

2

TreeSet with custom Comparator (descending order)

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

TreeSet<Integer> descendingNumbers = new TreeSet<>(Comparator.reverseOrder());
descendingNumbers.add(50);
descendingNumbers.add(10);
descendingNumbers.add(30);
descendingNumbers.add(10); // Duplicate

System.out.println("Numbers (sorted descending): " + descendingNumbers);
Output:
Numbers (sorted descending): [50, 30, 10]

A `Comparator` is provided to sort elements in reverse numerical order.

3

Using NavigableSet methods for range queries

import java.util.TreeSet;

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
numbers.add(50);

System.out.println("First element: " + numbers.first());
System.out.println("Last element: " + numbers.last());
System.out.println("Element <= 25: " + numbers.floor(25));
System.out.println("Element >= 35: " + numbers.ceiling(35));
System.out.println("Subset from 20 (inclusive) to 40 (exclusive): " + numbers.subSet(20, 40));
Output:
First element: 10 Last element: 50 Element <= 25: 20 Element >= 35: 40 Subset from 20 (inclusive) to 40 (exclusive): [20, 30]

Demonstrates `NavigableSet` methods like `first()`, `last()`, `floor()`, `ceiling()`, and `subSet()` for efficient access and range queries based on the sorted order.

Debug faster

Common Errors

1

NullPointerException with null elements

Cause: `TreeSet` does not allow `null` elements because it relies on element comparison (either natural ordering or a `Comparator`) to maintain its sorted structure. A `null` element cannot be compared.

Fix: Ensure that elements added to a `TreeSet` are never `null`. If `null` elements are a possibility, consider using `HashSet` if ordering is not critical, or handle `null` elements explicitly before insertion.

import java.util.TreeSet;

TreeSet<String> set = new TreeSet<>();
// set.add(null); // Throws NullPointerException

// Correct:
set.add("element");
System.out.println(set);

Runtime support

Compatibility

JVMN/AJava 1.2+

Source: Oracle Java Documentation

Common questions

Frequently Asked Questions

A Red-Black tree based implementation of the NavigableSet interface, providing unique, sorted elements and guaranteed log(n) time complexity for basic operations.

comparator: The comparator that will be used to order this set. If null, the natural ordering of the elements will be used.

NullPointerException with null elements: Ensure that elements added to a `TreeSet` are never `null`. If `null` elements are a possibility, consider using `HashSet` if ordering is not critical, or handle `null` elements explicitly before insertion.