Skip to content
Tutorials Center
My learning

Topics

Java Reference ยท Collections

The TreeSet class

Reference for java.util.TreeSet: a sorted set backed by a red-black tree, natural ordering or a Comparator, and floor, ceiling and range views.

TreeSet<E> keeps its elements sorted at all times. It is backed by a red-black tree, so add, remove and contains take O(log n) time, and iteration returns elements in ascending order. Besides the normal Set methods it offers navigation: the smallest and largest element, the closest element below or above a value, and live range views.

Order comes from the elements' natural ordering (Comparable) or from a Comparator passed to the constructor. Whichever you use also defines what "duplicate" means: two elements that compare as 0 are treated as the same.

Java
TreeSet<Integer> nums = new TreeSet<>(List.of(5, 1, 3));    // [1, 3, 5]
TreeSet<String> byLength = new TreeSet<>(Comparator.comparing(String::length));

Try it

Java Sorted order and navigation

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.

Java A comparator defines equality

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.

Syntax

Java
public class TreeSet<E> extends AbstractSet<E>
        implements NavigableSet<E>, Cloneable, java.io.Serializable
Constructor Description
TreeSet() Empty set using natural ordering.
TreeSet(Comparator<? super E> c) Empty set using the comparator.
TreeSet(Collection<? extends E> c) Natural ordering, filled from c.
TreeSet(SortedSet<E> s) Same elements and same comparator as s.
Member Description
first(), last() Smallest and largest. Throw NoSuchElementException when empty.
lower(e), floor(e), ceiling(e), higher(e) Neighbors of e: <, <=, >=, >. Return null if none.
pollFirst(), pollLast() Remove and return an end; null when empty.
headSet(to), tailSet(from), subSet(from, to) Live range views (variants take inclusive flags).
descendingSet(), descendingIterator() Reverse order.

Usage notes

  • Complexity: O(log n) for add, remove, contains, floor, ceiling and the other navigation methods. Range views are created in O(log n).
  • Consistency with equals: the comparator decides duplicates, not equals(). A comparator that ignores a field silently drops elements that differ in that field.
  • No null elements with natural ordering: add(null) throws NullPointerException. A custom comparator may accept null, but avoid it.
  • Elements must be mutually comparable, otherwise ClassCastException is thrown on insertion.
  • Views are live. headSet, tailSet and subSet reflect changes to the parent set, and inserting a value outside a view's range throws IllegalArgumentException.
  • Not synchronized. For concurrent use consider ConcurrentSkipListSet.
  • Do not mutate a field that takes part in the ordering after the element is inserted.
  • Java 21 also gives TreeSet the sequenced methods (getFirst, reversed, ...).