JAVA-201 · Lesson 6 of 12 · 21 min
TreeMap, TreeSet and ordering
▶ Video coming soon A video version of this lesson is on the way.
Odile's rental bikes go out from the spring, and the shop will need to answer questions like these: which booking for the cargo bike comes next after Saturday? Is the tandem free on any day between May 1 and May 7? What were the last three rentals? A HashMap can answer "what is booked on May 8?" in O(1), but it cannot answer "what comes next?" at all, because it keeps no order. The plan for Friday, February 26, 2027, after the reading week, is the sorted half of the framework: TreeMap and TreeSet.
A map that stays sorted
A TreeMap keeps its keys in sorted order at all times. Strings sort alphabetically, numbers numerically and dates chronologically, because each of those types has a natural ordering, as lesson 7 explains. Iterating over a TreeMap, or printing it, gives the entries in key order. The basic map methods are the same as HashMap's; what changes is the cost, O(log n) instead of O(1) on average, and what you get in return.
import java.time.LocalDate;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
TreeMap<LocalDate, String> cargo = new TreeMap<>();
cargo.put(LocalDate.of(2027, 5, 8), "Theo Park, 3 days");
cargo.put(LocalDate.of(2027, 4, 24), "Mei Lin, 2 days");
cargo.put(LocalDate.of(2027, 5, 1), "Ana Ruiz, 1 day");
cargo.put(LocalDate.of(2027, 4, 17), "Ravi Shah, 1 day");
for (var e : cargo.entrySet()) {
System.out.println(e.getKey() + " " + e.getValue());
}
System.out.println("first: " + cargo.firstKey() + ", last: " + cargo.lastKey());
}
}2027-04-17 Ravi Shah, 1 day 2027-04-24 Mei Lin, 2 days 2027-05-01 Ana Ruiz, 1 day 2027-05-08 Theo Park, 3 days first: 2027-04-17, last: 2027-05-08
What this code does
The bookings were put in a jumbled order, but the TreeMap returns them by date because LocalDate has a natural chronological order. firstKey and lastKey give the earliest and latest dates directly. A HashMap would have stored the same entries in no particular order.
Navigating: floor, ceiling, lower and higher
Because its keys are ordered, a TreeMap can find the nearest key to one you give it, even if that exact key is not present. floorKey(k) returns the greatest key less than or equal to k; ceilingKey(k) the least key greater than or equal to k. lowerKey and higherKey are the strict versions, never returning k itself. Each has an Entry version, such as ceilingEntry, which returns the key and value together, and all of them return null when there is no such key.
import java.time.LocalDate;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
TreeMap<LocalDate, String> cargo = new TreeMap<>();
cargo.put(LocalDate.of(2027, 4, 17), "Ravi Shah");
cargo.put(LocalDate.of(2027, 4, 24), "Mei Lin");
cargo.put(LocalDate.of(2027, 5, 1), "Ana Ruiz");
cargo.put(LocalDate.of(2027, 5, 8), "Theo Park");
LocalDate today = LocalDate.of(2027, 4, 26);
System.out.println("next booking after today: " + cargo.ceilingEntry(today));
System.out.println("most recent before today: " + cargo.floorEntry(today));
System.out.println("booking strictly after May 1: " + cargo.higherKey(LocalDate.of(2027, 5, 1)));
System.out.println("on or before May 1: " + cargo.floorKey(LocalDate.of(2027, 5, 1)));
System.out.println("before April 17: " + cargo.lowerKey(LocalDate.of(2027, 4, 17)));
}
}next booking after today: 2027-05-01=Ana Ruiz most recent before today: 2027-04-24=Mei Lin booking strictly after May 1: 2027-05-08 on or before May 1: 2027-05-01 before April 17: null
What this code does
ceilingEntry finds the first booking on or after April 26, which is Ana's on May 1, and floorEntry finds Mei's on April 24. higherKey skips May 1 itself because it is strict, while floorKey includes it. lowerKey returns null because nothing is booked before April 17.
Ranges: headMap, tailMap and subMap
A TreeMap can also give you a range of its entries as a view. headMap(k) holds the keys before k, tailMap(k) the keys from k on, and subMap(from, to) those in between. By default the lower bound is inclusive and the upper bound exclusive, the same convention as substring and subList, and versions with boolean arguments let you choose. The views are live: changes to the map show through them.
import java.time.LocalDate;
import java.util.NavigableMap;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
TreeMap<LocalDate, String> tandem = new TreeMap<>();
tandem.put(LocalDate.of(2027, 4, 30), "Lin family");
tandem.put(LocalDate.of(2027, 5, 3), "Ana Ruiz");
tandem.put(LocalDate.of(2027, 5, 6), "Theo Park");
tandem.put(LocalDate.of(2027, 5, 9), "Mei Lin");
LocalDate from = LocalDate.of(2027, 5, 1), to = LocalDate.of(2027, 5, 7);
NavigableMap<LocalDate, String> week = tandem.subMap(from, true, to, true);
System.out.println("May 1 to May 7: " + week);
System.out.println("before May 1: " + tandem.headMap(from));
System.out.println("May 7 onwards: " + tandem.tailMap(to, true));
tandem.put(LocalDate.of(2027, 5, 4), "Ravi Shah");
System.out.println("the week view now: " + week.keySet());
System.out.println("latest first: " + tandem.descendingMap().keySet());
}
}May 1 to May 7: {2027-05-03=Ana Ruiz, 2027-05-06=Theo Park}
before May 1: {2027-04-30=Lin family}
May 7 onwards: {2027-05-09=Mei Lin}
the week view now: [2027-05-03, 2027-05-04, 2027-05-06]
latest first: [2027-05-09, 2027-05-06, 2027-05-04, 2027-05-03, 2027-04-30]What this code does
subMap with both bounds inclusive gives the two bookings in the first week of May, and headMap and tailMap give the parts before and after. Because the view is live, Ravi's booking added later on May 4 appears in it without asking again. descendingMap shows the whole map in reverse order.
TreeSet
A TreeSet is to TreeMap what HashSet is to HashMap: a set of sorted elements stored as the keys of a tree map. It has the same navigation methods under shorter names: first, last, floor, ceiling, lower, higher, headSet, tailSet and subSet, plus pollFirst and pollLast, which remove and return the smallest or largest element. A TreeSet is the simplest way to keep a collection both free of duplicates and in order.
import java.util.List;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
TreeSet<Integer> spokeLengths = new TreeSet<>(List.of(296, 260, 302, 288, 296, 274));
System.out.println("in stock: " + spokeLengths);
int needed = 291;
System.out.println("shortest at least " + needed + ": " + spokeLengths.ceiling(needed));
System.out.println("longest at most " + needed + ": " + spokeLengths.floor(needed));
System.out.println("between 270 and 300: " + spokeLengths.subSet(270, true, 300, true));
System.out.println("take the longest: " + spokeLengths.pollLast() + ", left " + spokeLengths);
}
}in stock: [260, 274, 288, 296, 302] shortest at least 291: 296 longest at most 291: 288 between 270 and 300: [274, 288, 296] take the longest: 302, left [260, 274, 288, 296]
What this code does
The TreeSet drops the second 296 and keeps the lengths sorted. When a wheel needs a spoke of 291 mm, ceiling finds the closest length that is long enough and floor the closest that is not too long. pollLast removes and returns the largest value, 302.
Inside a TreeMap: a red-black tree
A TreeMap stores its entries in a binary search tree: each node has a key, a left child holding smaller keys and a right child holding larger keys. To find a key you start at the root and go left or right at each node, so the number of steps is the height of the tree. Lesson 10 builds such a tree from scratch and shows that a careless one can become a long chain. TreeMap avoids that by using a red-black tree, a kind of self-balancing tree that colors each node red or black and rotates parts of the tree after insertions and deletions so that no path is more than about twice as long as any other.
Balancing guarantees a height of O(log n), so get, put, remove and every navigation method are O(log n) in the worst case, not just on average. For Kofi's 612 parts that is at most about 20 comparisons, and for a million keys about 40. You never see the colors or rotations; you just get sorted order with predictable cost.
| Operation | HashMap | TreeMap |
|---|---|---|
| get, put, remove | O(1) on average | O(log n), guaranteed |
| Iterate in key order | not possible | O(n) |
| firstKey, lastKey | not available | O(log n) |
| floorKey, ceilingKey, subMap | not available | O(log n) plus the size of the range |
| Requirements on keys | good equals and hashCode | a natural order or a Comparator |
| null keys | one allowed | not allowed with natural ordering |
Choosing the order
A TreeMap or TreeSet sorts by the keys' natural ordering unless you give its constructor a Comparator, an object that decides the order of two values. Lesson 7 covers comparators in depth; one use is common enough to show now. String.CASE_INSENSITIVE_ORDER sorts strings ignoring case, and Comparator.reverseOrder() turns any natural order around.
import java.util.*;
public class Main {
public static void main(String[] args) {
List<String> names = List.of("bell", "Brake pads", "axle nut", "Chain");
System.out.println("natural order: " + new TreeSet<>(names));
TreeSet<String> ignoringCase = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
ignoringCase.addAll(names);
System.out.println("ignoring case: " + ignoringCase);
TreeMap<Integer, String> byCount = new TreeMap<>(Comparator.reverseOrder());
byCount.put(14, "tubes");
byCount.put(6, "pads");
byCount.put(22, "cable ends");
System.out.println("largest counts first: " + byCount);
}
}natural order: [Brake pads, Chain, axle nut, bell]
ignoring case: [axle nut, bell, Brake pads, Chain]
largest counts first: {22=cable ends, 14=tubes, 6=pads}What this code does
Natural order for Strings puts every capital letter before every lower-case letter, so Brake pads and Chain come first. The case-insensitive comparator sorts them as a person would expect. Comparator.reverseOrder makes a TreeMap that keeps its largest keys first.
When a comparator says two things are equal
A sorted set decides that two elements are the same when the comparator says they compare as equal, not when equals says so. If the comparator treats two different objects as equal, the set keeps only one of them, silently. The ordering should therefore be consistent with equals: compare(a, b) should be zero exactly when a.equals(b). A common way to guarantee it is to break ties with a second key that is unique.
import java.util.*;
public class Main {
public static void main(String[] args) {
record Part(String code, int count) {}
List<Part> parts = List.of(new Part("PAD-ROAD", 6), new Part("BELL", 6), new Part("TUBE-700x25", 14));
Set<Part> byCountOnly = new TreeSet<>(Comparator.comparingInt(Part::count));
byCountOnly.addAll(parts);
System.out.println("count only: " + byCountOnly.size() + " parts " + byCountOnly);
Set<Part> byCountThenCode = new TreeSet<>(
Comparator.comparingInt(Part::count).thenComparing(Part::code));
byCountThenCode.addAll(parts);
System.out.println("count, then code: " + byCountThenCode.size() + " parts " + byCountThenCode);
}
}count only: 2 parts [Part[code=PAD-ROAD, count=6], Part[code=TUBE-700x25, count=14]] count, then code: 3 parts [Part[code=BELL, count=6], Part[code=PAD-ROAD, count=6], Part[code=TUBE-700x25, count=14]]
What this code does
Ordering by count alone makes PAD-ROAD and BELL compare as equal, because both have 6, so the first set keeps only one of them. Breaking ties by the unique code keeps all three parts, lowest count first and then alphabetically. Always make a sorted set's comparator distinguish every element you want to keep.
A TreeMap also needs keys it can compare. Putting a key whose class has no natural order, with no comparator given, fails with ClassCastException on the first comparison. Records do not get a natural order automatically; they must implement Comparable, or the map must be given a Comparator.
import java.util.TreeSet;
public class Main {
record Bike(String name) {}
public static void main(String[] args) {
TreeSet<Bike> fleet = new TreeSet<>();
fleet.add(new Bike("City 1"));
System.out.println("added one");
fleet.add(new Bike("Cargo 1"));
}
}What this code does
Bike does not implement Comparable and the TreeSet was given no comparator, so it cannot decide where to put a Bike. The program stops with ClassCastException when the set tries to compare, here already on the first add. Give the set a comparator such as Comparator.comparing(Bike::name), or make Bike implement Comparable.
$ javac Main.java
$ java Main
Exception in thread "main" java.lang.ClassCastException: class Main$Bike cannot be cast to class java.lang.Comparable (Main$Bike is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
at java.base/java.util.TreeMap.compare(TreeMap.java:1604)
at java.base/java.util.TreeMap.addEntryToEmptyMap(TreeMap.java:811)
at java.base/java.util.TreeMap.put(TreeMap.java:820)
at java.base/java.util.TreeMap.put(TreeMap.java:569)
at java.base/java.util.TreeSet.add(TreeSet.java:259)
at Main.main(Main.java:8)Try it yourself
The next free date
Complete nextBooking so it returns the first booked date on or after from, or null if there is none, using ceilingKey.
The program should print next after April 26: 2027-05-01 and next after May 9: null.
import java.time.LocalDate;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
TreeMap<LocalDate, String> cargo = new TreeMap<>();
cargo.put(LocalDate.of(2027, 4, 24), "Mei Lin");
cargo.put(LocalDate.of(2027, 5, 1), "Ana Ruiz");
cargo.put(LocalDate.of(2027, 5, 8), "Theo Park");
System.out.println("next after April 26: " + nextBooking(cargo, LocalDate.of(2027, 4, 26)));
System.out.println("next after May 9: " + nextBooking(cargo, LocalDate.of(2027, 5, 9)));
}
static LocalDate nextBooking(TreeMap<LocalDate, String> bookings, LocalDate from) {
return bookings.firstKey();
}
}Try it yourself
Spokes in a range
Complete fits so it returns the spoke lengths from min to max, both inclusive, as a NavigableSet, using subSet.
The program should print [274, 288, 296].
import java.util.*;
public class Main {
public static void main(String[] args) {
TreeSet<Integer> lengths = new TreeSet<>(List.of(260, 274, 288, 296, 302));
System.out.println(fits(lengths, 270, 296));
}
static NavigableSet<Integer> fits(TreeSet<Integer> lengths, int min, int max) {
return lengths.headSet(max, false);
}
}Common mistakes
MistakeUsing a HashMap when you need the next or previous key.
InsteadUse a TreeMap and its floorKey, ceilingKey, lowerKey and higherKey methods.
MistakeForgetting that subMap and headMap exclude the upper bound by default.
InsteadUse the versions with boolean arguments, such as subMap(from, true, to, true), when you mean inclusive.
MistakeGiving a TreeSet a comparator that treats different elements as equal.
InsteadBreak ties with a unique field, such as thenComparing(Part::code).
MistakePutting objects with no natural order into a TreeSet without a comparator.
InsteadImplement Comparable or pass a Comparator to the constructor.
MistakeExpecting floorKey or ceilingKey to throw when nothing matches.
InsteadThey return null; check for it.
Summary and key terms
- A TreeMap keeps its keys sorted, by their natural ordering or by a Comparator given to its constructor, so iterating gives entries in key order.
- It can navigate: firstKey and lastKey, floorKey and ceilingKey, which may return the key itself, and lowerKey and higherKey, which never do; the Entry versions return key and value, and all return null when nothing matches. headMap, tailMap and subMap return live views of ranges, inclusive at the bottom and exclusive at the top unless you choose otherwise, and descendingMap reverses the order.
- A TreeSet is a sorted set with the same navigation under names such as floor, ceiling, subSet and pollFirst.
- Both are built on a red-black tree, a self-balancing binary search tree, so their operations are O(log n) in the worst case.
- A sorted collection treats elements as equal when its ordering says so, so the ordering should be consistent with equals.
- Keys with no order cause ClassCastException.
- TreeMap
- A map that keeps its keys in sorted order in a balanced tree.
- TreeSet
- A set that keeps its elements in sorted order.
- Natural ordering
- The order a type defines for itself by implementing Comparable.
- floorKey and ceilingKey
- Methods that find the nearest key at or below, or at or above, a given key.
- lowerKey and higherKey
- Methods that find the nearest key strictly below or above a given key.
- subMap
- A live view of the entries whose keys fall in a range.
- NavigableMap
- The interface for sorted maps with navigation methods.
- Binary search tree
- A tree in which each node's left side holds smaller keys and right side larger keys.
- Red-black tree
- A self-balancing binary search tree used by TreeMap.
- Self-balancing tree
- A tree that restructures itself to keep its height O(log n).
- Consistent with equals
- An ordering that compares two elements as equal exactly when equals says they are.
Practice problems
Work each problem on paper first, then reveal the answer to check.
Which method finds the first rental on or after a given date?
Show answer
ceilingKey, or ceilingEntry for the date and the booking together.
What is the difference between floorKey(k) and lowerKey(k)?
Show answer
floorKey may return k itself; lowerKey returns only keys strictly less than k.
Is the upper bound of subMap(from, to) included?
Show answer
No, unless you use the version with booleans and pass true.
What is the cost of get on a TreeMap with n keys?
Show answer
O(log n), guaranteed by the red-black tree.
Why might a TreeSet with a comparator on count alone lose parts?
Show answer
Parts with equal counts compare as equal, so only one is kept.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.