TreeMap and TreeSet

Keep keys or elements automatically sorted using TreeMap and TreeSet, backed by a red-black tree.

Overview

TreeMap and TreeSet keep their contents sorted at all times. TreeMap sorts by key; TreeSet sorts its elements. Both are backed by a red-black tree, giving O(log n) performance for add, remove, and contains. By default, sorting uses the natural ordering (Comparable). You can supply a custom Comparator to the constructor for a different order. Both implement NavigableMap and NavigableSet respectively, which provide powerful range and neighbour-finding methods like firstKey, lastKey, headMap, tailMap, floorEntry, and ceilingEntry.

Key Points

•TreeMap keeps entries sorted by key (natural order or custom Comparator)
•TreeSet keeps elements sorted (natural order or custom Comparator)
•O(log n) for put, get, remove, add, contains
•firstKey/lastKey, firstEntry/lastEntry to get the extremes
•headMap(toKey) gives a view of keys strictly less than toKey
•tailMap(fromKey) gives a view of keys >= fromKey
•floorKey(k) is the largest key <= k; ceilingKey(k) is the smallest key >= k
•Use when you need sorted iteration or range queries

Examples

TreeMap sorted by key

import java.util.TreeMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("Charlie", 85);
        scores.put("Alice", 92);
        scores.put("Bob", 78);
        scores.put("Diana", 96);

        // Keys always come out sorted
        System.out.println(scores); // {Alice=92, Bob=78, Charlie=85, Diana=96}

        System.out.println("First: " + scores.firstEntry()); // Alice=92
        System.out.println("Last: " + scores.lastEntry());   // Diana=96

        // Range: keys from Alice (inclusive) to Charlie (exclusive)
        System.out.println(scores.subMap("Alice", "Charlie")); // {Alice=92, Bob=78}
    }
}

The iteration order of TreeMap is always ascending key order. subMap, headMap, tailMap return live views backed by the original map.

TreeSet sorted elements

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> primes = new TreeSet<>();
        primes.add(7);
        primes.add(2);
        primes.add(13);
        primes.add(5);
        primes.add(3);
        primes.add(11);

        System.out.println(primes); // [2, 3, 5, 7, 11, 13]
        System.out.println("First: " + primes.first()); // 2
        System.out.println("Last: " + primes.last());   // 13

        // Largest prime <= 6
        System.out.println("Floor of 6: " + primes.floor(6));   // 5
        // Smallest prime >= 6
        System.out.println("Ceiling of 6: " + primes.ceiling(6)); // 7

        // Primes less than 8
        System.out.println("Head (<8): " + primes.headSet(8)); // [2, 3, 5, 7]
    }
}

floor and ceiling are powerful for nearest-value queries. headSet and tailSet return live subsets.

Custom sort order with Comparator

import java.util.TreeMap;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        // Sort keys in reverse order
        TreeMap<String, Integer> reversed = new TreeMap<>(Comparator.reverseOrder());
        reversed.put("Banana", 2);
        reversed.put("Apple", 5);
        reversed.put("Cherry", 1);

        System.out.println(reversed); // {Cherry=1, Banana=2, Apple=5}
        System.out.println("First: " + reversed.firstKey()); // Cherry
    }
}

Pass a Comparator to the constructor to override the natural ordering. Comparator.reverseOrder() gives descending order for Comparable types.

Common Mistakes

Adding an element that does not implement Comparable (and providing no Comparator) throws ClassCastException at runtime
Forgetting that range views (headMap, tailMap, subMap) are live: changes to the view reflect in the original map and vice versa
Using TreeMap or TreeSet when you do not need sorting, paying O(log n) when HashMap or HashSet would give O(1)

Note

Use TreeMap when building a frequency map that you later want to iterate in alphabetical or numeric order. It saves a separate sort step.

TreeMap and TreeSet

Overview

Key Points

Examples

Common Mistakes

Note

Exercises

Knowledge Check

What is the time complexity of get and put in a TreeMap?