How does a TreeSet know how to order its elements, and what happens if it can't compare them?
answer
- Two sources: Comparable (natural) or Comparator (constructor)
- Comparator beats Comparable when both present
- No comparator + non-Comparable type = ClassCastException at runtime
- Ordering should be consistent with equals or you drop elements
- Add a tie-breaker (thenComparing) to keep distinct equal-rank items
basics
~10 sIt orders elements either by their natural ordering (the type implements Comparable) or by a Comparator you pass to the constructor. If neither exists, adding an element throws a ClassCastException.
solid answer
~50 sA TreeSet must compare elements to place them in the tree. It uses one of two sources: the element type's natural ordering via Comparable.compareTo, or a Comparator supplied to the TreeSet constructor. The Comparator, when present, wins and is used for all comparisons. If you build a TreeSet with no Comparator and add an element whose class does not implement Comparable, the add fails with a ClassCastException at runtime — not at compile time. A subtle but important rule: the chosen ordering must be consistent with equals(); if compare/compareTo returns 0 for two objects that equals() says are different, the TreeSet treats them as the same element, so the second is dropped. This can silently lose data. Also, under natural ordering TreeSet rejects null because it would call compareTo on null and throw NullPointerException; a null-tolerant Comparator can change that.
code
java · 12 lines// Single-field comparator silently drops distinct equal-rank items
TreeSet<Person> bad = new TreeSet<>(Comparator.comparing(Person::age));
bad.add(new Person("Alice", 30));
bad.add(new Person("Bob", 30)); // compares 0 with Alice -> dropped!
System.out.println(bad.size()); // 1
// Fix: total order with a tie-breaker
TreeSet<Person> good = new TreeSet<>(
Comparator.comparing(Person::age).thenComparing(Person::name));
good.add(new Person("Alice", 30));
good.add(new Person("Bob", 30));
System.out.println(good.size()); // 2go deeper
Knows you need Comparable or a Comparator, and that missing comparison logic causes an error.
Explains that Comparator overrides natural ordering, the ClassCastException is at runtime, and null is rejected under natural ordering.
Articulates the consistent-with-equals contract, why single-field comparators silently drop elements, and the tie-breaker fix.
Reasons about ordering as a domain invariant — total vs partial orders, stability of sort keys, and the data-loss risk of an inconsistent comparator across the codebase.
## The core requirement A TreeSet is a **sorted** set, so for every pair of elements it must answer: which is smaller, larger, or are they equal? It needs a comparison rule. There are exactly two ways to give it one. ## Option 1 — Natural ordering (Comparable) If the element's class implements the **`Comparable<T>`** interface, it has a method `int compareTo(T other)` that returns: - a **negative** number if `this` is less than `other`, - **zero** if they are considered equal in order, - a **positive** number if `this` is greater. Many built-in types already implement it: `Integer`, `Long`, `String` (lexicographic), `LocalDate`, enums, etc. So `new TreeSet<Integer>()` just works. ## Option 2 — A Comparator A **`Comparator<T>`** is a separate object whose `int compare(T a, T b)` returns the same negative/zero/positive contract. You pass it to the constructor: ```java new TreeSet<>(Comparator.comparing(Person::getAge)); ``` When a Comparator is supplied, **it is used for everything** and the element's own `compareTo` is ignored. ## What if neither exists? If you create a TreeSet with **no** Comparator and add an element whose class is **not** `Comparable`, the TreeSet tries to cast it to `Comparable` to call `compareTo`, and you get a **`ClassCastException`** — at **runtime**, on the `add` call (specifically once there are ≥2 elements to compare, or on the first add in modern JDKs). The compiler cannot catch this because the TreeSet's generic type does not require Comparable. ## The 'consistent with equals' contract The `Comparable`/`Comparator` docs strongly recommend the ordering be **consistent with equals**: `a.compareTo(b) == 0` should hold exactly when `a.equals(b)`. A sorted set like TreeSet **defines element equality by the comparison returning 0**, ignoring `equals()` entirely. So if you sort `Person` only by age, two different people of the same age compare as 0, and the TreeSet keeps only one of them — silently dropping the other. The fix is to make the comparator a **total tie-breaker**, e.g. `comparing(Person::getAge).thenComparing(Person::getId)`. ## Nulls Under natural ordering, `add(null)` invokes `null.compareTo(...)` → **`NullPointerException`**. A Comparator that explicitly tolerates null (e.g. `Comparator.nullsFirst(...)`) can permit nulls, but this is unusual. ## Mental checklist 1. Does the type implement Comparable? If yes, natural ordering is available. 2. Do I need a different order, or to sort a non-Comparable type? Pass a Comparator. 3. Is my ordering a *total* order that breaks ties on every distinguishing field? If not, I may drop elements.
- You store Person objects in a TreeSet sorted only by lastName and notice some people disappear. Why, and how do you fix it?People with the same lastName compare as 0, so the TreeSet treats them as duplicates and keeps one. Fix by extending the comparator with a unique tie-breaker, e.g. Comparator.comparing(Person::getLastName).thenComparing(Person::getId).
- At what point does a non-Comparable element trigger the ClassCastException?On an add that requires a comparison — i.e. when the TreeSet must cast the element to Comparable to position it. It is a runtime exception, never caught at compile time.
saying these in an interview costs you the question
- Expecting a compile error when the type isn't Comparable (it's a runtime ClassCastException)
- Thinking the element's compareTo is still used when a Comparator was supplied
- Sorting by a single non-unique field and being surprised elements vanish
- Assuming equals() decides duplicates in a TreeSet