Java TreeSet Comparator: Ordering and Behavior

A TreeSet is a sorted collection backed by a red-black tree. Every element is placed according to an ordering rule, not insertion order. By default, that rule comes from the element type's Comparable implementation. When the element type does not implement Comparable, or when natural ordering is not the ordering you need, you supply a java treeset comparator at construction time.

The constructor that accepts a Comparator is the one to use:

TreeSet<String> words = new TreeSet<>(Comparator.reverseOrder());

The comparator is stored internally and used for every insertion, deletion, and lookup. The set never calls equals or hashCode to locate an element; it uses the comparator to navigate the tree. That single fact explains most of the surprising behavior you will encounter with TreeSet.

Writing a Basic Comparator

Suppose you have a record representing a task with a priority and a name:

record Task(int priority, String name) {}

Natural ordering is not defined for this record, so you cannot create a TreeSet<Task> without a comparator. The simplest approach is a lambda:

TreeSet<Task> tasks = new TreeSet<>(
    (a, b) -> Integer.compare(a.priority(), b.priority())
);

The comparator must return a negative integer, zero, or a positive integer depending on whether the first argument is less than, equal to, or greater than the second. Integer.compare is the correct way to compare primitive ints; subtracting one value from the other can overflow and produce the wrong sign.

Using Method References and Chained Comparators

A lambda that delegates to an existing method can be replaced with a method reference:

TreeSet<Task> tasks = new TreeSet<>(Comparator.comparingInt(Task::priority));

When two tasks have the same priority, the comparator returns zero, and TreeSet treats the second task as a duplicate. The second task is silently discarded. If you want equal-priority tasks to coexist, chain a secondary comparator:

TreeSet<Task> tasks = new TreeSet<>(
    Comparator.comparingInt(Task::priority)
              .thenComparing(Task::name)
);

Comparator.thenComparing and its primitive variants (thenComparingInt, thenComparingLong, thenComparingDouble) let you build a multi-level ordering without writing nested if statements.

Why Comparator Must Be Consistent with equals

TreeSet uses the comparator for all element comparisons, including membership tests. If the comparator returns zero for two elements that equals considers different, the set will treat them as the same element. Consider:

record Person(String id, String name) {}

TreeSet<Person> people = new TreeSet<>(
    Comparator.comparing(Person::id)
);

people.add(new Person("A1", "Alice"));
people.add(new Person("A1", "Bob"));

System.out.println(people.size()); // 1

The second add is ignored because the comparator sees the same id. This is the documented behavior: a TreeSet with a comparator that is inconsistent with equals behaves as if it used the comparator for equality. If that is not what you want, either include the distinguishing fields in the comparator or use a different collection.

Handling Null Elements

TreeSet does not allow null elements by default. The natural ordering comparator throws NullPointerException when it encounters null, and most custom comparators do too. If null must be allowed, the comparator has to handle it explicitly:

TreeSet<String> set = new TreeSet<>(
    Comparator.nullsFirst(Comparator.naturalOrder())
);

set.add(null);
set.add("apple");

Comparator.nullsFirst and Comparator.nullsLast wrap an existing comparator and define where null values are placed. The wrapped comparator is never invoked for a null argument, so it will not throw. Note that nullsFirst with a comparator that itself does not handle null is safe because the wrapper checks for null before delegating.

Performance and Runtime Behavior

Every operation on a TreeSet is O(log n) because of the red-black tree structure. The comparator is invoked multiple times per operation, not once. During an insertion, the tree performs a series of comparisons to locate the correct leaf position, and each comparison calls the comparator. A comparator that is expensive, such as one that parses strings or queries a database, will make the set noticeably slower.

The comparator is also invoked during iteration in the sense that the tree maintains its structure through comparisons, but iteration itself walks the tree in order without re-sorting. This means the cost of ordering is paid at insertion time, not at iteration time.

If the comparator is stateful or depends on mutable fields of the elements, the tree can become corrupted. Changing a field that the comparator reads after the element has been inserted can break the tree's invariants, causing elements to be unreachable or iteration to produce wrong order. The comparator should be stateless and deterministic, and elements should be effectively immutable with respect to the fields the comparator reads.

Common Mistakes and Their Consequences

One frequent mistake is using subtraction to compare int values:

Comparator<Task> bad = (a, b) -> a.priority() - b.priority();

When the difference overflows Integer.MIN_VALUE, the sign flips and the comparator returns the wrong result. Integer.compare avoids this.

Another mistake is assuming TreeSet preserves insertion order for equal elements. It does not. When the comparator returns zero, the new element is not inserted, regardless of whether it came before or after the existing element.

A third issue is using a comparator that depends on mutable state. If the comparator reads a field that changes after insertion, the tree's ordering invariant is violated, and contains, remove, and iteration can all behave incorrectly. The fix is to design elements so the fields used by the comparator are final or never modified after insertion.

Choosing Between TreeSet and Other Collections

A TreeSet with a comparator is the right choice when you need a continuously sorted set with logarithmic operations and you control the ordering rule. If you only need to sort once and never modify the set, collecting into a List and sorting is simpler and faster. If you need fast lookup by hash and ordering is secondary, a HashSet or LinkedHashSet is more appropriate. If you need duplicate elements, none of the Set implementations work; use a sorted List or a PriorityQueue depending on whether you need full ordering or only the minimum element.

The decision comes down to whether the collection must remain sorted while elements are added and removed. If yes, TreeSet with a well-designed comparator is the standard choice. If no, avoid the tree overhead.