Navigable Collections: TreeSet, TreeMap, and the Comparator Contract

Checkout needs every SKU in sorted order, the next order id after o-100, and every mapping whose key sits in a range. A HashMap stores the pairs. It will not give them back sorted, and it has no ceiling.

Reach for TreeSet and TreeMap when the collection must stay sorted while it mutates. The Collections roadmap owns fail-fast, views vs copies, and why Map is not a Collection. This post is the sorted contracts, the Navigable methods, and the Comparator that has to stay consistent with equals. The tree shape is a red-black tree — height stays O(log n) even when ids arrive in order. This post does not teach rotations.

The lab types are the series’ checkout records:

public record Order(
        String id,
        String customerEmail,
        List<LineItem> items,
        BigDecimal total,
        boolean active) {}

public record LineItem(String sku, int quantity, BigDecimal unitPrice) {}

Sorted and Navigable are one family

SortedSet / NavigableSet and SortedMap / NavigableMap are one interview story, not four types you pick independently. Java 6 added the Navigable layer so ceiling, floor, and inclusive range bounds are methods, not a loop you write by hand.

Interface	Extends	Job
`SortedSet<E>`	`Set<E>`	Unique elements, ordered by `Comparable` or a `Comparator`
`NavigableSet<E>`	`SortedSet<E>`	Plus closest-match and poll at the ends
`SortedMap<K,V>`	`Map<K,V>`	Mappings ordered by key
`NavigableMap<K,V>`	`SortedMap<K,V>`	Plus closest-match and poll on keys

TreeSet is the JDK NavigableSet. TreeMap is the JDK NavigableMap. Program to the interface on fields; new the tree.

NavigableSet<String> skus = new TreeSet<>();
NavigableMap<String, Order> byId = new TreeMap<>();

One red-black tree, two facades. TreeSet is a TreeMap whose values are a dummy object. add is put(element, PRESENT). contains is containsKey. There is no second layout to memorize.

Natural order vs a Comparator

The no-arg constructors sort by the element’s (or key’s) natural order: compareTo on a Comparable. Strings, BigDecimal, and Integer already are. Order is a record — it is not Comparable unless you make it one.

NavigableSet<String> skus = new TreeSet<>();
skus.add("SKU-200");
skus.add("SKU-100");
skus.add("SKU-150");
System.out.println(skus);

[SKU-100, SKU-150, SKU-200]

Pass a Comparator when natural order is the wrong order, or when the type is not Comparable. The functional-interfaces hub only names Comparator as a SAM outside java.util.function. Collections own the rest: compare, the factories, and consistency with equals.

@FunctionalInterface
public interface Comparator<T> {
    int compare(T a, T b);
}

compare(a, b) is negative when a sorts before b, zero when they are the same for this ordering, and positive when a sorts after. The usual factories:

Factory	Job
`comparing(Function)`	Sort by a key extracted from the element
`thenComparing(...)`	Break ties without collapsing two elements
`reversed()`	Flip an existing comparator
`naturalOrder()` / `reverseOrder()`	The type’s `compareTo`, or its reverse
`nullsFirst` / `nullsLast`	Park `null` at an end (possible; a smell as a key policy)
`comparingInt` / `comparingLong` / `comparingDouble`	Skip boxing on a primitive key

LineItem widget = new LineItem("SKU-100", 2, new BigDecimal("9.99"));
LineItem gadget = new LineItem("SKU-200", 1, new BigDecimal("15.00"));
Order cheap = new Order("o-2", "ada@ex.com", List.of(gadget), new BigDecimal("15.00"), true);
Order spendy = new Order("o-1", "ada@ex.com", List.of(widget), new BigDecimal("19.98"), true);

NavigableSet<Order> byTotal = new TreeSet<>(
        Comparator.comparing(Order::total).thenComparing(Order::id));
byTotal.add(spendy);
byTotal.add(cheap);
System.out.println(byTotal.stream().map(Order::id).toList());

[o-2, o-1]

comparator() on the set or map returns that Comparator, or null when the tree is using natural order. Copy constructors new TreeMap<>(sortedMap) keep the source’s comparator.

thenComparing(Order::id) is not decoration — uniqueness in a TreeSet is compare == 0, not equals. Drop the id tie-break and two orders with the same total become one element. The second add returns false and the first order stays. You put something you will not find.

Consistent with equals, or the tree lies

Set and Map are specified in terms of equals. TreeSet and TreeMap never call equals to place a node. They call compareTo or compare. The ordering is consistent with equals when:

(compare(a, b) == 0) == a.equals(b)

Break that and the tree is still a well-defined sorted structure. It is no longer an honest Set or Map. contains / get walk the comparator. Two keys the comparator calls equal are one entry, even when equals says they are different. Two keys equals calls the same are two entries if compare disagrees — and then contains of the “equal” object misses.

BigDecimal is the classic: compareTo is numeric; equals also checks scale.

BigDecimal oneScale1 = new BigDecimal("1.0");
BigDecimal oneScale2 = new BigDecimal("1.00");
System.out.println(oneScale1.compareTo(oneScale2)); // 0
System.out.println(oneScale1.equals(oneScale2));    // false

NavigableSet<BigDecimal> tree = new TreeSet<>();
tree.add(oneScale1);
tree.add(oneScale2);
System.out.println(tree.size());                    // 1
System.out.println(tree.contains(oneScale2));       // true — compareTo, not equals

Set<BigDecimal> hashed = new HashSet<>();
hashed.add(oneScale1);
hashed.add(oneScale2);
System.out.println(hashed.size());                  // 2

The same trap on a map: you put 1.0 and get(1.00) hits because the tree asked compareTo. A HashMap would miss.

NavigableMap<BigDecimal, String> labels = new TreeMap<>();
labels.put(new BigDecimal("1.0"), "ten percent");
System.out.println(labels.get(new BigDecimal("1.00")));

ten percent

String.CASE_INSENSITIVE_ORDER is the same shape: "SKU" and "sku" compare equal and are not equals. A TreeSet with that comparator keeps one of them.

Prefer a TreeMap keyed by the field that is actually unique — Order.id, LineItem.sku — over a TreeSet<Order> whose comparator picks a subset of the record. Record equals uses every component. A comparator on total alone is inconsistent by construction.

Null keys

Natural-order TreeMap and TreeSet reject a null key or element: compareTo would NPE, so put / add throw NullPointerException first. HashMap allows one null key. That difference is in the hub matrix.

NavigableMap<String, Order> byId = new TreeMap<>();
byId.put("o-1", spendy);
// byId.put(null, spendy); // NullPointerException

A Comparator that defines a null policy can accept null:

NavigableMap<String, Order> withNull = new TreeMap<>(
        Comparator.nullsFirst(String::compareTo));
withNull.put(null, spendy); // compiles and stores

A null-tolerant comparator is possible and a smell as a key policy. Sorted iteration now has a ghost at one end, and every caller has to remember whether firstKey() can be null. Prefer a real key. Values in a TreeMap may be null; that is a different slot.

The API you actually call

Sorted methods first; Navigable adds the closest-match and inclusive overloads. Empty-tree reads: first / last / firstKey / lastKey throw NoSuchElementException. poll* and ceiling* return null.

Method	Set	Map	Notes
`first()` / `last()`	yes	—	Least / greatest element
`firstKey()` / `lastKey()`	—	yes	Least / greatest key
`firstEntry()` / `lastEntry()`	—	yes	Navigable; `null` if empty
`headSet(to)` / `headMap(to)`	yes	yes	Keys strictly less than `to`
`tailSet(from)` / `tailMap(from)`	yes	yes	Keys greater than or equal to `from`
`subSet(from, to)` / `subMap(from, to)`	yes	yes	`[from, to)` — from inclusive, to exclusive
`head` / `tail` / `sub*` + booleans	yes	yes	Navigable inclusive/exclusive overloads
`ceiling` / `floor`	yes	`ceilingKey` / `floorKey`	Closest ≥ / ≤
`higher` / `lower`	yes	`higherKey` / `lowerKey`	Closest > / <
`pollFirst` / `pollLast`	yes	`pollFirstEntry` / `pollLastEntry`	Remove and return the end
`descendingSet` / `descendingMap`	yes	yes	Reverse-ordered view
`navigableKeySet()`	—	yes	Keys as a `NavigableSet`

Map also has ceilingEntry / floorEntry / higherEntry / lowerEntry when you need the value with the bound.

Range views, not copies

headSet, tailSet, subSet and the map twins are views. A structural change through the view writes through. A copy would be new TreeSet<>(byId.subMap("o-1", "o-9").keySet()).

NavigableMap<String, Order> byId = new TreeMap<>();
byId.put("o-1", spendy);
byId.put("o-2", cheap);
byId.put("o-9", spendy);

NavigableMap<String, Order> open = byId.subMap("o-1", true, "o-9", false);
System.out.println(open.keySet());
open.put("o-3", cheap);
System.out.println(byId.keySet());
// open.put("o-9", cheap); // IllegalArgumentException — outside the range

[o-1, o-2]
[o-1, o-2, o-3]

The half-open subMap(from, to) overload is [from, to). People trip on headMap being exclusive and tailMap being inclusive. Use the boolean overloads when the bound must sit inside the view.

System.out.println(byId.headMap("o-2").keySet());           // [o-1]
System.out.println(byId.headMap("o-2", true).keySet());     // [o-1, o-2]
System.out.println(byId.tailMap("o-2").keySet());           // [o-2, o-3, o-9]
System.out.println(byId.tailMap("o-2", false).keySet());    // [o-3, o-9]

SKU strings sort lexicographically. "SKU-100" sits before "SKU-2". If the range you mean is numeric, do not pretend a String key is an integer.

Ceiling vs higher (floor vs lower)

Warehouse asks: the first SKU at or after SKU-150, and the first SKU after SKU-150. That is ceiling vs higher. Inclusive vs exclusive of the argument. floor / lower are the same idea looking down.

NavigableSet<String> skus = new TreeSet<>(List.of("SKU-100", "SKU-150", "SKU-200"));

System.out.println(skus.ceiling("SKU-150")); // SKU-150  (≥)
System.out.println(skus.higher("SKU-150"));  // SKU-200  (>)
System.out.println(skus.floor("SKU-150"));   // SKU-150  (≤)
System.out.println(skus.lower("SKU-150"));   // SKU-100  (<)
System.out.println(skus.ceiling("SKU-125")); // SKU-150
System.out.println(skus.higher("SKU-200"));  // null

On a map, ceilingKey("o-1") is the next id at or after that string; ceilingEntry brings the Order with it. These are O(log n) walks, not a scan.

Poll and descending

pollFirst / pollLast (and pollFirstEntry / pollLastEntry) remove the end. Empty → null, no exception. Useful when the tree is the work list ordered by key — still a tree, not a queue.

NavigableMap<String, Order> byId = new TreeMap<>();
byId.put("o-1", spendy);
byId.put("o-2", cheap);

Map.Entry<String, Order> first = byId.pollFirstEntry();
System.out.println(first.getKey()); // o-1
System.out.println(byId.keySet());  // [o-2]

descendingSet / descendingMap reverse the encounter order. They are live views: add through the descending set still lands in comparator order in the backing tree. Iteration of the view is greatest-to-least.

NavigableSet<String> skus = new TreeSet<>(List.of("SKU-100", "SKU-150", "SKU-200"));
NavigableSet<String> newestFirst = skus.descendingSet();
System.out.println(newestFirst); // [SKU-200, SKU-150, SKU-100]
newestFirst.add("SKU-125");
System.out.println(skus);        // [SKU-100, SKU-125, SKU-150, SKU-200]

Sequenced on Java 21

TreeSet is a SequencedSet. TreeMap is a SequencedMap. getFirst / getLast / reversed / pollFirst match the sorted ends. Sequenced Collections owns the shared names.

Sorted types do not honor addFirst / addLast / putFirst / putLast. Position is the comparator’s job. Those methods throw UnsupportedOperationException. Use add / put and let the tree place the node.

SequencedSet<String> skus = new TreeSet<>(List.of("SKU-200", "SKU-100"));
System.out.println(skus.getFirst()); // SKU-100
System.out.println(skus.getLast());  // SKU-200
skus.add("SKU-150");                 // ok — comparator places it
// skus.addFirst("SKU-000");         // UnsupportedOperationException

Not a HashMap, not a skip list, not a heap

Type	Order	Hot lookup	Threads
`HashMap` / `HashSet`	none	expected `O(1)`	no
`TreeMap` / `TreeSet`	sorted by key / element	`O(log n)`	no
`ConcurrentSkipListMap`	sorted	`O(log n)` expected	concurrent
`PriorityQueue`	heap order on poll only	`O(1)` peek of the extreme	no

Wrong answer: “TreeMap is a HashMap that keeps keys sorted.” A hash table does not keep a search tree on the side. TreeMap never hashes. get is a compare walk of height O(log n), worst case, not expected O(1). Iteration is in-order by key. You do not sort a HashMap on every request to fake this.

Need a concurrent sorted map? One sentence: ConcurrentSkipListMap is a skip list with Navigable methods, not a red-black tree — details in Concurrent Queues and Skip Lists. Need the next-best element without sorted iteration? That is a heap: PriorityQueue. iterator() on a PriorityQueue is not priority order. Do not copy into a TreeSet “to sort” unless you wanted a set.

TreeMap is not thread-safe. Iterators are fail-fast (hub). Matching the hot operation still matters: a tree of twenty SKUs loses to a sorted ArrayList you binary-search after one sort. The tree wins when the collection stays sorted across inserts and deletes.

Interview lens

Interviewers want one story: sorted contracts, a tree, a comparator that does not fight equals.

What to draw. Set → SortedSet → NavigableSet → TreeSet. Beside it, Map → SortedMap → NavigableMap → TreeMap. Write “red-black, O(log n)” under both. Draw HashMap off to the side with “no order, expected O(1).”

Typical questions:

Question	Honest answer
Complexity of `TreeMap.get` / `put` / `remove`?	`O(log n)` worst case. Height is bounded.
What is the layout?	A red-black tree. Not a hash table. Rotations live in the DS post.
`Comparator` vs `Comparable`?	Natural order is `compareTo` on the element. A constructor `Comparator` replaces that for this collection only.
Why does inconsistent comparison lose entries?	The tree treats `compare == 0` as “same key.” `equals` is not consulted. Two `BigDecimal` scales, or two `Order`s with the same `total` and no `thenComparing(id)`, collapse.
`ceiling` vs `higher`?	`ceiling` is ≥; `higher` is >. `floor` / `lower` are ≤ and <.
Is `TreeMap` a `HashMap` with sorting?	No. Different layout, different equality rule, different complexity.
Iteration order?	Sorted by the comparator (or natural order). Always.

They may ask whether TreeSet is a TreeMap. Yes: dummy values. They may ask null. Natural order rejects it; a null-friendly Comparator can allow it and you should almost never.

Cheat sheet

Layout       red-black tree; TreeSet = TreeMap + dummy value
Complexity   get / put / remove / ceiling  O(log n)
Order        comparator or Comparable; iteration is sorted
Uniqueness   compare == 0, not equals
Consistent   (compare(a,b)==0) == a.equals(b)  or the Set/Map contract lies
Null keys    natural order → NPE; Comparator.nullsFirst works, smell
Range        head / tail / sub are views; [from, to) unless booleans
Closest      ceiling ≥  higher >  floor ≤  lower <
Ends         first/last throw if empty; poll* returns null
Reverse      descendingSet / descendingMap — views
Java 21      Sequenced; addFirst/putFirst throw on sorted types

vs HashMap   no sort, expected O(1), equals/hashCode
vs skip list ConcurrentSkipListMap when another thread looks
vs heap      PriorityQueue polls an extreme; it is not a sorted set

Do:

Key a TreeMap by Order.id or LineItem.sku when that field is the order you mean.
Tie-break thenComparing(Order::id) if the set element is the whole Order.
Use ceiling / subMap instead of sorting a HashMap on every request.

Don’t:

Call TreeMap “a sorted HashMap.”
Compare only total and expect two orders with the same total to both survive.
Treat PriorityQueue iteration as sorted, or headMap as inclusive without checking.

Wrap-up

TreeSet and TreeMap keep keys sorted in a red-black tree. get, put, remove, and the Navigable closest-match methods are O(log n). Range methods return views. Iteration is in-order. The comparator (or compareTo) is the equality the tree believes — keep it consistent with equals, or you will not find what you put. That is not a HashMap with extra steps.

When the key universe is a small enum rather than a sorted string, hashing is the wrong tax. The next post is that universe.

Next optional step in the series A closed set of keys does not need a hash or a tree. EnumSet and EnumMap: Universe-Sized Keys Without a Hash

Navigable Collections:TreeSet, TreeMap, and the Comparator Contract

Sorted and Navigable are one family

Natural order vs a Comparator

Consistent with equals, or the tree lies

Null keys

The API you actually call

Range views, not copies

Ceiling vs higher (floor vs lower)

Poll and descending

Sequenced on Java 21

Not a HashMap, not a skip list, not a heap

Interview lens

Cheat sheet

Wrap-up

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup

Sorted and Navigable are one family

Natural order vs a Comparator

Consistent with equals, or the tree lies

Null keys

The API you actually call

Range views, not copies

Ceiling vs higher (floor vs lower)

Poll and descending

Sequenced on Java 21

Not a HashMap, not a skip list, not a heap

Interview lens

Cheat sheet

Wrap-up

Related posts

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup