Java TreeSet

Introduction#

In the Java Collection Framework, TreeSet is a class that implements the NavigableSet interface and indirectly implements the SortedSet interface, which in turn extends the Set interface. It stores elements in a sorted (natural or custom) order and is part of the java.util package. Internally, it is backed by a Red-Black Tree, a self-balancing binary search tree. Unlike HashSet and LinkedHashSet, TreeSet does not allow null elements and ensures that elements are always sorted.

Key Features#

• Stores unique elements like any Set.
• Maintains elements in sorted order.
• Implements SortedSet and NavigableSet interfaces.
• Does not allow null elements.
• Backed by a Red-Black Tree.

Classes Implemented by TreeSet#

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
    
public interface NavigableSet<E> extends SortedSet<E>

Here TreeSet implements NavigableSet and NavigableSet extends SortedSet, therefore TreeSet Implements SortedSet interface indirectly.

SortedSet Interface#

SortedSet is a subinterface of Set that maintains elements in a sorted order.

A TreeSet implements this interface to keep elements automatically sorted in natural order or using a custom comparator.

public interface SortedSet<E> extends Set<E> {
    Comparator<? super E> comparator();
    E first();
    E last();
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
    SortedSet<E> subSet(E fromElement, E toElement);
}

Constructors#

TreeSet<E> set = new TreeSet<>();
TreeSet<E> set = new TreeSet<>(Comparator<? super E> comparator);
TreeSet<E> set = new TreeSet<>(Collection<? extends E> collection);
TreeSet<E> set = new TreeSet<>(SortedSet<E> sortedSet);

Explanation:#

• The default constructor creates an empty TreeSet that will be sorted according to the natural ordering of its elements.
• The constructor with Comparator allows for custom sorting.
• The constructor with Collection copies elements and maintains the sorted order.
• The constructor with SortedSet creates a TreeSet with the same ordering as the provided sorted set.

Commonly Used Methods#

Example: Basic Usage#

import java.util.TreeSet;

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

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

Output:#

TreeSet: [10, 20, 30, 40]

Explanation:#

The numbers are automatically sorted in ascending order (natural ordering). Duplicates are not allowed, and TreeSet ensures sorted uniqueness.

Example: Navigable Methods#

import java.util.TreeSet;

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

        System.out.println("First: " + set.first());
        System.out.println("Last: " + set.last());
        System.out.println("HeadSet(30): " + set.headSet(30));
        System.out.println("TailSet(20): " + set.tailSet(20));
        System.out.println("SubSet(10, 30): " + set.subSet(10, 30));
    }
}

Output:#

First: 10
Last: 40
HeadSet(30): [10, 20]
TailSet(20): [20, 30, 40]
SubSet(10, 30): [10, 20]

Explanation:#

• first() returns the lowest element in the set.
• last() returns the highest element.
• headSet(30) returns elements strictly less than 30.
• tailSet(20) returns elements greater than or equal to 20.
• subSet(10, 30) returns elements from 10 (inclusive) to 30 (exclusive).

Performance#

Explanation:#

Due to the Red-Black Tree structure, insertions, deletions, and lookups are all logarithmic in time. Iterating through the set is linear.

Null Handling#

import java.util.TreeSet;

public class NullHandling {
    public static void main(String[] args) {
        TreeSet<String> set = new TreeSet<>();
        set.add(null); // Throws NullPointerException
    }
}

Explanation:#

TreeSet does not allow null elements because it uses comparisons to sort elements, and comparing null with other objects throws a NullPointerException.

Custom Comparator#

You can sort elements in a custom order using a comparator:

import java.util.*;

public class CustomComparatorExample {
    public static void main(String[] args) {
        TreeSet<String> set = new TreeSet<>(Comparator.reverseOrder());
        set.add("Apple");
        set.add("Banana");
        set.add("Mango");

        System.out.println("Descending Order: " + set);
    }
}

Output:#

Descending Order: [Mango, Banana, Apple]

Explanation:#

We passed a reverse order comparator to the TreeSet constructor, so the elements are sorted in descending order.

Key Takeaways:#

• TreeSet stores unique, sorted elements.
• Sorting can be natural (by default) or custom (via Comparator).
• Null elements are not allowed.
• Operations like add, remove, and search take O(log n) time.

Use TreeSet when:

• You need sorted order and uniqueness.
• You don't need to allow nulls.
• Slightly lower performance than HashSet is acceptable in exchange for automatic ordering.

Conclusion#

In this blog, we explored the TreeSet class in detail. We discussed its characteristics, method usage, and how it maintains elements in sorted order using a Red-Black Tree. We also looked at performance, null handling, and how to apply custom sorting with a comparator.