Today, we’re diving into an essential part of the Java Collections Framework: the TreeSet class. If you’ve been working with Java for a while, you’ve likely encountered HashSet for its blazing fast operations or LinkedHashSet for its predictable iteration order. But what if you need a set that not only stores unique elements but also keeps them in a sorted order?

Enter TreeSet – your go-to for naturally ordered or custom-ordered sets. Let’s explore its functionalities, advantages, and how to effectively use it in your Java applications.

What is a Java TreeSet?

In Java, a TreeSet is a concrete implementation of the Set interface, which in turn extends the SortedSet and NavigableSet interfaces. This means it provides all the capabilities of a standard Set (no duplicate elements) along with the power of ordering and navigation.

Under the hood, TreeSet is backed by a TreeMap. This is a crucial detail, as TreeMap stores its elements in a Red-Black tree structure. This self-balancing binary search tree ensures that operations like adding, removing, and searching elements have a time complexity of O(log n) – making it very efficient for large datasets.

Key Characteristics of TreeSet:

• Stores Unique Elements: Like all Set implementations, TreeSet does not allow duplicate elements. If you try to add an element that already exists, the operation will be ignored, and the set will remain unchanged.
• Maintains Sorted Order: This is its defining feature. Elements are stored in ascending order by default, either based on their natural ordering or a custom comparator you provide.
• No Null Elements: TreeSet does not permit null elements. Attempting to add a null will result in a NullPointerException. This is because null cannot be compared with other elements.
• Non-Synchronized: TreeSet is not thread-safe. If multiple threads access a TreeSet concurrently and at least one thread modifies it, external synchronization must be performed. You can use Collections.synchronizedSortedSet() for this purpose.
• Performance: Operations like add(), remove(), and contains() have an average time complexity of O(log n).

How TreeSet Determines Order

There are two primary ways TreeSet can sort its elements:

1. Natural Ordering

If you don’t provide a custom comparator, TreeSet relies on the “natural ordering” of the elements. This means the objects you store in the TreeSet must implement the Comparable interface. Many built-in Java classes, such as String, Integer, Double, etc., already implement Comparable.

Example with Natural Ordering:

import java.util.TreeSet;

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

        numbers.add(50);
        numbers.add(10);
        numbers.add(30);
        numbers.add(20);
        numbers.add(40);
        numbers.add(30); // Duplicate, will not be added

        System.out.println("Numbers in natural order: " + numbers); // Output: [10, 20, 30, 40, 50]

        TreeSet names = new TreeSet<>();
        names.add("Ankur");
        names.add("Bimal");
        names.add("Chirag");
        names.add("Ankur"); // Duplicate

        System.out.println("Names in natural order: " + names); // Output: [Ankur, Bimal, Chirag]
    }
}
        

2. Custom Ordering (Comparator)

If your elements don’t have a natural ordering or you want to sort them in a different way (e.g., descending order, by a specific field in a custom object), you can provide a Comparator when creating the TreeSet.

Example with Custom Ordering (Descending):

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

public class TreeSetCustomOrderingExample {
    public static void main(String[] args) {
        // Create a TreeSet with a custom comparator for reverse order
        TreeSet descendingNumbers = new TreeSet<>(Comparator.reverseOrder());

        descendingNumbers.add(50);
        descendingNumbers.add(10);
        descendingNumbers.add(30);
        descendingNumbers.add(20);
        descendingNumbers.add(40);

        System.out.println("Numbers in descending order: " + descendingNumbers); // Output: [50, 40, 30, 20, 10]

        // Custom object example
        class Employee implements Comparable {
            String name;
            int id;

            public Employee(String name, int id) {
                this.name = name;
                this.id = id;
            }

            @Override
            public String toString() {
                return "Employee{" + "name='" + name + '\'' + ", id=" + id + '}';
            }

            // Natural ordering by ID
            @Override
            public int compareTo(Employee other) {
                return Integer.compare(this.id, other.id);
            }
        }

        // Sort Employees by Name (using a custom Comparator)
        TreeSet employeesSortedByName = new TreeSet<>(new Comparator() {
            @Override
            public int compare(Employee e1, Employee e2) {
                return e1.name.compareTo(e2.name);
            }
        });

        employeesSortedByName.add(new Employee("Ankur", 101));
        employeesSortedByName.add(new Employee("Bimal", 103));
        employeesSortedByName.add(new Employee("Chirag", 102));

        System.out.println("Employees sorted by name: " + employeesSortedByName);
        // Output: [Employee{name='Ankur', id=101}, Employee{name='Bimal', id=103}, Employee{name='Chirag', id=102}]

        // Sort Employees by ID (using natural ordering defined in Employee class)
        TreeSet employeesSortedById = new TreeSet<>(); // Uses Employee's compareTo()
        employeesSortedById.add(new Employee("Ankur", 101));
        employeesSortedById.add(new Employee("Bimal", 103));
        employeesSortedById.add(new Employee("Chirag", 102));

        System.out.println("Employees sorted by ID: " + employeesSortedById);
        // Output: [Employee{name='Ankur', id=101}, Employee{name='Chirag', id=102}, Employee{name='Bimal', id=103}]
    }
}
        

Common TreeSet Constructors

Here are the frequently used constructors for TreeSet:

• TreeSet(): Constructs an empty tree set that will be sorted according to the natural ordering of its elements.
• TreeSet(Collection c): Constructs a new tree set containing the elements in the specified collection, sorted according to the natural ordering of its elements.
• TreeSet(Comparator comparator): Constructs a new, empty tree set, sorted according to the specified comparator.
• TreeSet(SortedSet s): Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set.

Key Methods of TreeSet

Beyond the standard Set methods like add(), remove(), contains(), size(), isEmpty(), etc., TreeSet (due to its NavigableSet and SortedSet interfaces) offers powerful methods for navigation and retrieval:

From SortedSet:

• first(): Returns the first (lowest) element currently in the set.
• last(): Returns the last (highest) element currently in the set.
• headSet(E toElement): Returns a view of the portion of this set whose elements are strictly less than toElement.
• tailSet(E fromElement): Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
• subSet(E fromElement, E toElement): Returns a view of the portion of this set whose elements range from fromElement (inclusive) to toElement (exclusive).

From NavigableSet:

• lower(E e): Returns the greatest element in this set strictly less than e, or null if there is no such element.
• floor(E e): Returns the greatest element in this set less than or equal to e, or null if there is no such element.
• ceiling(E e): Returns the least element in this set greater than or equal to e, or null if there is no such element.
• higher(E e): Returns the least element in this set strictly greater than e, or null if there is no such element.
• pollFirst(): Retrieves and removes the first (lowest) element, or returns null if this set is empty.
• pollLast(): Retrieves and removes the last (highest) element, or returns null if this set is empty.
• descendingSet(): Returns a reverse order view of the elements contained in this set.
• descendingIterator(): Returns an iterator over the elements in this set in descending order.

Example of Navigation Methods:

import java.util.TreeSet;

public class TreeSetNavigationExample {
    public static void main(String[] args) {
        TreeSet numbers = new TreeSet<>();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(40);
        numbers.add(50);

        System.out.println("Original TreeSet: " + numbers); // [10, 20, 30, 40, 50]

        System.out.println("First element: " + numbers.first());   // 10
        System.out.println("Last element: " + numbers.last());    // 50

        System.out.println("Lower than 30: " + numbers.lower(30));  // 20
        System.out.println("Floor of 30: " + numbers.floor(30));  // 30
        System.out.println("Ceiling of 30: " + numbers.ceiling(30)); // 30
        System.out.println("Higher than 30: " + numbers.higher(30)); // 40

        System.out.println("Poll First: " + numbers.pollFirst());   // 10 (removed)
        System.out.println("TreeSet after pollFirst: " + numbers); // [20, 30, 40, 50]

        System.out.println("Poll Last: " + numbers.pollLast());    // 50 (removed)
        System.out.println("TreeSet after pollLast: " + numbers);  // [20, 30, 40]

        System.out.println("HeadSet (elements < 40): " + numbers.headSet(40)); // [20, 30]
        System.out.println("TailSet (elements >= 30): " + numbers.tailSet(30)); // [30, 40]
        System.out.println("SubSet (30 inclusive, 40 exclusive): " + numbers.subSet(30, 40)); // [30]

        System.out.println("Descending Set: " + numbers.descendingSet()); // [40, 30, 20]
    }
}
        

When to Use TreeSet

Consider using TreeSet in situations where:

• You need to store unique elements.
• You require the elements to be maintained in a sorted order (either natural or custom).
• You frequently need to perform range queries (e.g., finding all elements between X and Y).
• You need to efficiently retrieve the smallest or largest element.

TreeSet vs. HashSet vs. LinkedHashSet

Let’s quickly compare TreeSet with its Set siblings to understand their respective strengths:

Performance Considerations

While TreeSet offers the benefit of sorted data, its operations (add, remove, contains) are O(log n) compared to the O(1) average performance of HashSet and LinkedHashSet. For very large datasets where sorting is not a primary requirement, or if you constantly need to add/remove elements and the order is not critical, HashSet will generally be faster.

However, if sorted order or range queries are essential, the O(log n) performance of TreeSet is still very efficient and a small trade-off for the valuable functionality it provides.

Thread Safety

As mentioned earlier, TreeSet is not thread-safe. If you are using a TreeSet in a multi-threaded environment where multiple threads might modify it, you must externalize synchronization. You can achieve this using:

import java.util.Collections;
import java.util.SortedSet;
import java.util.TreeSet;

public class SynchronizedTreeSetExample {
    public static void main(String[] args) {
        TreeSet regularTreeSet = new TreeSet<>();

        // Get a synchronized view of the TreeSet
        SortedSet synchronizedTreeSet = Collections.synchronizedSortedSet(regularTreeSet);

        // Now, all modifications to synchronizedTreeSet will be thread-safe
        synchronizedTreeSet.add("Apple");
        synchronizedTreeSet.add("Banana");
        synchronizedTreeSet.add("Orange");

        System.out.println("Synchronized TreeSet: " + synchronizedTreeSet);
    }
}
        

It’s important to synchronize on the returned SortedSet object, not its internal TreeSet directly.

Conclusion

TreeSet is a powerful and versatile collection class in Java, offering the best of both worlds: unique elements and sorted order. Whether you’re dealing with a simple list of sorted numbers or complex custom objects that need specific ordering, TreeSet provides an efficient and elegant solution. Understanding its underlying mechanism (Red-Black tree via TreeMap) and its specific methods will empower you to make informed decisions about when and how to use it effectively in your Java applications.

Do you frequently use TreeSet in your projects? Share your experiences and favorite use cases in the comments below!