TreeSet

TL;DR

• TreeSet is an implementation of the NavigableSet (and SortedSet) interface.
• It guarantees no duplicates and stores elements in sorted (ascending) order.
• Operations like add, remove, and contains take $O(\log n)$ time.
• It does not allow null elements.

Concept

Under the hood, a TreeSet is backed by a TreeMap, which itself is implemented using a Red-Black Tree (a self-balancing binary search tree).

Because it uses a tree structure, elements are automatically sorted as they are inserted. To do this, the elements must be comparable.
You can define sorting in two ways:

1. Natural Ordering: The elements inserted must implement the Comparable interface.
2. Custom Ordering: You can provide a custom Comparator to the TreeSet constructor.

Examples

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        // Natural Ordering (Alphabetical)
        TreeSet<String> names = new TreeSet<>();
        names.add("Zach");
        names.add("Alice");
        names.add("Bob");
        
        System.out.println(names); // [Alice, Bob, Zach]
        
        // NavigableSet methods (very powerful)
        System.out.println("First: " + names.first());       // Alice
        System.out.println("Last: " + names.last());         // Zach
        System.out.println("Before Bob: " + names.lower("Bob")); // Alice
        System.out.println("After Bob: " + names.higher("Bob")); // Zach
        
        // Custom Ordering (Descending)
        TreeSet<Integer> numbers = new TreeSet<>((a, b) -> b.compareTo(a));
        numbers.add(10);
        numbers.add(5);
        numbers.add(20);
        
        System.out.println(numbers); // [20, 10, 5]
    }
}

Interview Questions

Q: Why does TreeSet throw a NullPointerException if you try to add null?
A: To maintain the sorted structure, the Red-Black tree must compare every new element against existing elements (using .compareTo() or a Comparator). You cannot compare null to an object; calling .compareTo() on null throws a NullPointerException.

Q: Can you add a custom object to a TreeSet if it does not implement Comparable?
A: If you try to add a custom object (like Person) that does not implement Comparable to a default TreeSet, you will get a ClassCastException at runtime. The TreeSet won’t know how to sort them. To fix this, you must either make Person implement Comparable, or pass a Comparator<Person> into the TreeSet’s constructor.