Skip to content
Tutorials Center
My learning

Topics

Lesson 86 of 201 ยท Collections

TreeMap and TreeSet

Learn Java TreeMap and TreeSet - sorted keys, first/last, floor/ceiling/higher/lower, headMap, tailMap and subMap ranges, NavigableMap and custom comparators.

A HashMap answers one question brilliantly: "what is stored under this exact key?" It has no idea which key is the smallest, which key comes right after 42, or which entries fall between March 1 and March 31. For those questions you need a collection that keeps its keys sorted.

TreeMap and TreeSet are those collections. They store elements in a balanced binary search tree (a red-black tree), so the elements are always in order, and every operation takes O(log n) time: about 20 steps for a million elements. In exchange for being a little slower than hashing, they unlock a whole set of "navigation" methods: smallest and largest, nearest match below or above a value, and live views of ranges. This lesson covers all of them, plus custom orderings and the comparator mistake that silently deletes data.

Sorted by default

Put elements in any order; they come out sorted. Strings sort alphabetically (by Unicode value, so uppercase before lowercase), numbers numerically, dates chronologically. This is their natural ordering, defined by the Comparable interface (see Sorting with Comparable and Comparator).

Java Everything comes out sorted

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Like every set, a TreeSet drops duplicates. TreeMap behaves like any other Map (put, get, remove, getOrDefault, merge all work as in HashMap), so you can switch a HashMap to a TreeMap the moment you need sorted output.

Declare the variable as TreeMap/TreeSet (or the interfaces NavigableMap/NavigableSet) when you want the navigation methods below. A plain Map or Set type hides them.

These four methods find the nearest element to a value you give, even if that value isn't in the collection:

TreeSet TreeMap Returns
floor(x) floorKey(x), floorEntry(x) the greatest element โ‰ค x
ceiling(x) ceilingKey(x), ceilingEntry(x) the smallest element โ‰ฅ x
lower(x) lowerKey(x), lowerEntry(x) the greatest element < x
higher(x) higherKey(x), higherEntry(x) the smallest element > x

All of them return null when nothing qualifies, so check the result before you unbox it into an int.

Java Nearest values around a target

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

floor and ceiling include an exact match; lower and higher skip it. With need = 32 the floor and ceiling are both 32, while lower is 16 and higher is 64.

A lookup table with floorEntry

floorEntry turns a TreeMap into a range lookup table. Store the lower bound of each range as the key; the floor entry of any value is the range it falls into. No chain of if/else needed:

Java Grade boundaries and shipping rates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Because the table starts at 0, every non-negative score has a floor entry. If you can receive values below the first key, floorEntry returns null, so handle that case.

first, last and polling

Method On an empty collection
first(), last() (set), firstKey(), lastKey() (map) throws NoSuchElementException
firstEntry(), lastEntry() (map) returns null
pollFirst(), pollLast() (set), pollFirstEntry(), pollLastEntry() (map) returns null

The poll methods remove and return the smallest or largest element. That makes a TreeMap a handy priority structure when you also need lookups by key, or when you need both ends:

Java Processing a schedule in time order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Range views: headMap, tailMap and subMap

A TreeMap can hand you a view of just part of itself. The view isn't a copy: it's a window onto the original map, so it's created in O(log n), and changes in either one show up in the other.

Method Keys in the view
headMap(to) < to
headMap(to, true) โ‰ค to
tailMap(from) โ‰ฅ from
tailMap(from, false) > from
subMap(from, to) from โ‰ค key < to
subMap(from, fromInclusive, to, toInclusive) you choose both ends
descendingMap() all keys, largest first

TreeSet has the same methods named headSet, tailSet, subSet and descendingSet. The default is the usual Java convention: the start is inclusive and the end is exclusive, just like substring or List.subList.

Java Querying a range of dates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The last part fails on purpose: a range view only accepts keys inside its range, and putting a March date into the February view throws IllegalArgumentException.

Two details about the return types: the two-argument methods (headMap(to), subMap(from, to)) return the older SortedMap interface, while the versions with inclusive flags return NavigableMap, which still has floorKey, pollFirstEntry and the rest. If you want navigation methods on the view, use the flag versions.

Range views make "count elements between a and b" or "delete everything older than x" one-liners:

Java
int between = scores.subSet(70, true, 80, true).size();   // scores from 70 to 80
log.headMap(cutoff).clear();                               // drop entries before cutoff

Custom ordering with a Comparator

Pass a Comparator to the constructor to sort by anything you like. Comparator.reverseOrder() flips the natural order; Comparator.comparing(...) sorts objects by a property:

Java Reverse, by length and by a record field

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Notice the tie-breakers. Without thenComparing(Comparator.naturalOrder()), "pear" and "kiwi" (both length 4) would count as the same element, and one of them would vanish. That brings us to the most important rule of this lesson.

The comparator decides what "equal" means

A TreeSet never calls equals. Two elements are duplicates when the comparator returns 0 for them. If your comparator treats different objects as equal, the tree throws one of them away without a word:

Java A comparator that loses data

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The same applies to TreeMap keys: a put with a key the comparator considers equal replaces the value of the existing entry and keeps the old key. Sometimes that's exactly what you want (a case-insensitive map of HTTP headers, for example). When it isn't, add tie-breakers until the comparator only returns 0 for objects that really are equal. The Java docs call this being consistent with equals.

Rules and pitfalls

  • Elements must be comparable. Without a comparator, elements must implement Comparable. Adding a plain object throws ClassCastException at runtime (on the first add in current versions).
  • No null keys with natural ordering: put(null, ...) throws NullPointerException. null values are fine in a TreeMap.
  • Don't mutate keys. Like hash keys, a tree element filed by its score gets lost if the score changes while it's inside. Remove, change, re-add.
  • Not thread-safe. For a sorted concurrent map, use ConcurrentSkipListMap/ConcurrentSkipListSet (Concurrent Collections).
  • No putFirst/addFirst. TreeMap and TreeSet are sequenced collections in Java 21 (getFirst(), reversed() and friends work), but the tree decides where elements go, so addFirst, addLast, putFirst and putLast throw UnsupportedOperationException.

TreeMap vs HashMap

HashMap TreeMap
get, put, remove O(1) average O(log n)
Iteration order unspecified sorted
Navigation and ranges no yes
Key requirements equals + hashCode Comparable or a Comparator
null keys one allowed not with natural ordering

If you only need sorted output once, at the end, it's often faster to fill a HashMap and sort its entries when printing. Choose TreeMap when the sorted order or the nearest-key queries are needed all along. Choosing the Right Collection compares all the options.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. For TreeSet<Integer> s holding [10, 20, 30], what do s.floor(25) and s.higher(30) return?

    floor(25) is the greatest element less than or equal to 25, which is 20. higher(30) needs an element strictly greater than 30, and there is none, so it returns null.
  2. 2. A TreeMap has keys 1 through 10. How many keys are in map.subMap(3, 7)?

    The two-argument subMap includes the start and excludes the end, so it holds 3, 4, 5 and 6.
  3. 3. A TreeSet uses Comparator.comparingInt(String::length). What happens when you add "cat" and then "dog"?

    TreeSet treats elements as duplicates when the comparator returns 0. Both strings have length 3, so add("dog") returns false.
  4. 4. You clear the view returned by sales.tailMap(cutoff). What happens to sales?

    Range views are live windows onto the original map, so clearing the view removes those entries from the map itself.
  5. 5. What does new TreeMap<String, Integer>().firstKey() do?

    firstKey and lastKey throw on an empty map. firstEntry, lastEntry and the poll methods return null instead.

Summary

  • TreeMap and TreeSet keep elements sorted in a red-black tree; basic operations are O(log n).
  • The order is the natural ordering (Comparable) or a Comparator you pass to the constructor.
  • floor/ceiling find the nearest element at or below/above a value; lower/higher exclude exact matches; all return null when nothing fits.
  • floorEntry makes range lookup tables (grades, price bands) trivial.
  • headMap, tailMap, subMap and descendingMap (and their set versions) are live views; start bounds are inclusive and end bounds exclusive by default.
  • The comparator defines equality: a comparator that returns 0 for different objects silently drops elements, so add tie-breakers.

Next: Iterators and ListIterator, where you'll see how every for-each loop really works and how to remove elements safely while looping.