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

Runtime & versions

Java Virtual Machine. Feature availability depends on the language and runtime version used by your project; consult the official reference below.

Java Language Specification

Specifications & further reading