Codectionary / Developer documentation / Java

TreeMap & TreeSet

TreeMap and TreeSet are sorted collections backed by a red-black tree, automatically keeping their keys (or elements) in ascending order at all times. This ordering comes at a cost - operations run in logarithmic time rather than the constant time of HashMap/HashSet - but it's invaluable when you need sorted iteration, range queries, or to quickly find the smallest or largest element.

Syntax

TreeMap<K, V> map = new TreeMap<>();\nTreeSet<T> set = new TreeSet<>();

Examples

TreeMap: Automatically Sorted Keys

Entries are always iterated in ascending key order, with no manual sorting needed.

import java.util.TreeMap;

TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("Charlie", 78);
scores.put("Alice", 85);
scores.put("Bob", 92);

System.out.println(scores);  // {Alice=85, Bob=92, Charlie=78} - sorted by key

TreeMap Navigation Methods

TreeMap offers useful methods for finding entries relative to a given key.

import java.util.TreeMap;

TreeMap<Integer, String> events = new TreeMap<>();
events.put(2020, "Started university");
events.put(2023, "Started placement search");
events.put(2026, "Graduating");

System.out.println(events.firstKey());        // 2020
System.out.println(events.lastKey());          // 2026
System.out.println(events.ceilingKey(2022));    // 2023 (smallest key >= 2022)
System.out.println(events.floorKey(2022));       // 2020 (largest key <= 2022)

TreeSet: Automatically Sorted Unique Elements

TreeSet combines uniqueness (like HashSet) with automatic sorting.

import java.util.TreeSet;

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(1);
numbers.add(3);
numbers.add(1);  // duplicate, ignored

System.out.println(numbers);        // [1, 3, 5] - sorted automatically
System.out.println(numbers.first()); // 1
System.out.println(numbers.last());   // 5

Custom Sort Order with a Comparator

Both TreeMap and TreeSet can accept a Comparator for custom ordering, like descending instead of ascending.

import java.util.TreeSet;
import java.util.Comparator;

TreeSet<Integer> descending = new TreeSet<>(Comparator.reverseOrder());
descending.add(5);
descending.add(1);
descending.add(3);

System.out.println(descending);  // [5, 3, 1]

Best practices

  • Use TreeMap/TreeSet when you need entries kept in sorted order at all times, or need range/navigation queries like firstKey() and ceilingKey()
  • Use HashMap/HashSet instead when you just need fast lookups and do not care about ordering - they are faster for basic operations
  • Ensure keys/elements are either naturally Comparable (like String, Integer) or provide a Comparator when constructing the TreeMap/TreeSet
  • Remember TreeMap/TreeSet operations run in O(log n) time, slower than the average O(1) of HashMap/HashSet, due to maintaining sort order

At a glance

Purpose
General-purpose application development
File extension
.java
Runs in
Java Virtual Machine
Usually used with
JDK and Java libraries

Specifications & further reading

Related Java documentation

ArrayList
ArrayList is a resizable array implementation of the List interface, part of java.util. Unlike a plain array, an ArrayList automatically grows as elements are added, and it provides a rich set of methods for adding, removing, searching, and iterating. Since generics require object types, an ArrayList of primitives (like int) actually stores their wrapper class (Integer) via autoboxing.LinkedList
LinkedList is a doubly-linked list implementation of both the List and Deque interfaces. Unlike ArrayList, it stores elements as individual nodes linked to their neighbors, which makes inserting and removing elements at the beginning or middle much faster, at the cost of slower random access by index. Because it implements Deque, LinkedList can also be used directly as a stack or queue.HashMap
HashMap stores data as key-value pairs, offering constant-time (average case) lookup, insertion, and deletion by key, backed by a hash table. Keys must be unique - adding a value with an existing key overwrites the previous value. HashMap does not guarantee any particular ordering of its entries, unlike LinkedHashMap (which preserves insertion order) or TreeMap (which keeps keys sorted).HashSet
HashSet is a collection that stores unique elements with no guaranteed ordering, backed by a HashMap internally. Adding a duplicate element has no effect, since HashSet automatically enforces uniqueness. It provides constant-time (average case) performance for adding, removing, and checking membership, making it ideal for deduplication and fast lookups.