TreeSet in Java

Introduction

In the Java Collections Framework, TreeSet is an implementation of the Set interface that uses a TreeMap under the hood to store its elements. Unlike HashSet, which provides no guarantee regarding the order of elements, a TreeSet stores its elements in a sorted, ascending order according to their natural ordering or a provided Comparator.

TreeSet is the data structure of choice when you need a unique collection of elements that must be kept constantly sorted, allowing for rapid retrieval of ranges of data and closest-match queries.

Internal Mechanics: Backed by TreeMap

When you instantiate a TreeSet, Java internally creates a TreeMap.

• The elements you add to the TreeSet are stored as the keys in the backing TreeMap.
• The values in the TreeMap are mapped to a constant dummy object (PRESENT).

Because TreeMap is built on a Red-Black Tree (a self-balancing binary search tree), TreeSet inherits its performance characteristics. It guarantees O(log n) time complexity for basic operations (add, remove, and contains).

Creating and Initializing a TreeSet

1. Natural Ordering

For elements to be stored in a TreeSet without a custom comparator, the elements' class must implement the Comparable interface.

import java.util.Set;
import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        Set<Integer> numbers = new TreeSet<>();
        
        numbers.add(50);
        numbers.add(10);
        numbers.add(30);
        numbers.add(10); // Duplicate, will be ignored
        
        // Output will be strictly sorted: [10, 30, 50]
        System.out.println(numbers);
    }
}

2. Custom Ordering with Comparator

If you want to sort objects in a non-standard way, or if the class doesn't implement Comparable, you can pass a Comparator into the TreeSet constructor.

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

public class CustomOrderExample {
    public static void main(String[] args) {
        // Sort strings by their length instead of alphabetical order
        TreeSet<String> words = new TreeSet<>(Comparator.comparing(String::length));
        
        words.add("Banana");
        words.add("Apple");
        words.add("Kiwi");
        
        System.out.println(words); 
        // Output: [Kiwi, Apple, Banana]
    }
}

NavigableSet Operations

TreeSet implements the NavigableSet interface, offering powerful methods for searching and extracting subsets based on ranges.

• first() / last(): Returns the lowest / highest element.
• lower(E e) / higher(E e): Returns the greatest element strictly less than, or the least element strictly greater than the given element.
• floor(E e) / ceiling(E e): Returns the greatest element less than or equal to, or the least element greater than or equal to the given element.
• subSet(fromElement, toElement): Returns a view of the portion of this set whose elements range from fromElement to toElement.

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

System.out.println(treeSet.higher(25));   // 30
System.out.println(treeSet.lower(25));    // 20
System.out.println(treeSet.subSet(20, 45)); // [20, 30, 40]

Thread Safety

TreeSet is not synchronized. If multiple threads access it concurrently and at least one thread modifies the set, it must be synchronized externally.

SortedSet<T> syncTreeSet = Collections.synchronizedSortedSet(new TreeSet<T>());

For highly concurrent environments requiring a sorted set, ConcurrentSkipListSet is the recommended alternative.

Summary

• Underlying Data Structure: NavigableMap (specifically, a TreeMap).
• Time Complexity: O(log n) for add, remove, and contains.
• Duplicates: Not allowed. Adding a duplicate returns false.
• Null Elements: Adding null to a TreeSet that uses natural ordering will throw a NullPointerException.