How Do TreeMap and TreeSet Stay Sorted?

Both are backed by a red-black tree, a self-balancing binary search tree. The tree invariant is that every node's key is greater than all keys in its left subtree and less than all keys in its right subtree, which makes lookup, insertion and deletion O(log n) rather than the O(n) of a sorted list. The red-black colouring is what keeps the tree balanced: after every insertion or deletion the algorithm recolours and rotates nodes so that the longest path from the root to a leaf never exceeds twice the shortest, which is what stops a naive binary search tree from degenerating into a list.

The practical difference from a HashMap is the ordering guarantee. A TreeMap iterates in sorted key order and a TreeSet in sorted element order, every time, with no extra work. That makes them the right choice for range queries — everything between two keys, everything greater than a key — because the tree structure supports them directly, whereas a HashMap would require scanning the entire entry set.

The cost is that comparison is not free. Each operation performs O(log n) comparisons, and each comparison runs your comparator or your Comparable implementation. A HashMap computes a hash once and then compares a handful of candidates; a TreeMap compares on every step of the descent.

Two more details worth knowing. TreeMap and TreeSet reject null keys — a null has no position in an ordering. And the iteration order of a TreeMap is the sorted order of its keys, not the order of insertion, which is the first thing people check when they are surprised by an unexpectedly sorted output.

You pass a Comparator to the constructor, and the structure uses it for every comparison instead of the elements' own Comparable implementation. The comparator interface has one method, compare, returning a negative number, zero or a positive number — never use subtraction, because it overflows.

Modern Java makes chaining easy. Comparator.comparing and Comparator.comparingInt build a comparator from a key extractor, and thenComparing adds a tie-breaker, and reversed flips the whole chain. That reads far better than the anonymous Comparator classes the framework used to require.

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

public class Main {
    public static void main(String[] args) {
        // Age descending, then name ascending.
        Comparator<Person> byAgeThenName = Comparator
                .comparingInt(Person::getAge).reversed()
                .thenComparing(Person::getName);

        TreeSet<Person> people = new TreeSet<>(byAgeThenName);
        people.add(new Person("Grace", 45));
        people.add(new Person("Ada", 36));
        people.add(new Person("Alan", 45));

        System.out.println("by age desc, then name:");
        for (Person p : people) {
            System.out.println("  " + p.getName() + " " + p.getAge());
        }

        // A TreeMap with a custom comparator for the keys.
        TreeMap<String, Integer> scores = new TreeMap<>(Comparator.reverseOrder());
        scores.put("b", 2);
        scores.put("a", 1);
        System.out.println("reverse keys  : " + scores);
    }
}

class Person {
    private final String name;
    private final int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    String getName() {
        return name;
    }

    int getAge() {
        return age;
    }
}

The output shows the chained comparator at work. The set is ordered by age descending, so Grace and Alan come before Ada, and the two forty-fives are then broken by name — Alan before Grace. The TreeMap with a reversed comparator prints its keys in descending order.

One important detail: a TreeSet stores only one instance of each element, and it decides which one to keep using the comparator. If two elements compare as equal, the second one added is discarded, not replaced. With the comparator above, two people with the same age and the same name would collide, and only the first would survive.

They are the map and set flavours of the same underlying structure. A TreeMap stores key-value pairs, with the keys sorted. A TreeSet stores elements only, with those elements sorted. Both use a red-black tree, both are O(log n) for lookup, insertion and removal, and both reject null keys or elements because null has no position in an ordering.

The choice follows the same logic as between HashMap and HashSet. Use a TreeMap when you need to look things up by key and want ordered iteration or range queries. Use a TreeSet when you have a collection of values that must stay sorted and unique.

import java.util.TreeMap;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        // A TreeMap: sorted keys, values alongside.
        TreeMap<String, Integer> ages = new TreeMap<>();
        ages.put("Charlie", 40);
        ages.put("Alice", 30);
        ages.put("Bob", 35);
        System.out.println("map in order : " + ages);
        System.out.println("first key    : " + ages.firstKey());
        System.out.println("last key     : " + ages.lastKey());

        // A TreeSet: sorted unique elements.
        TreeSet<String> names = new TreeSet<>();
        names.add("Charlie");
        names.add("Alice");
        names.add("Alice");
        System.out.println("set in order : " + names);
        System.out.println("size         : " + names.size());
    }
}

The output shows the ordering guarantee in both structures — the map prints its entries sorted by key, and the set prints its elements sorted with the duplicate removed. The firstKey and lastKey methods are available on TreeMap but not on TreeSet, which instead offers first and last for the elements themselves and headSet and tailSet for the range views.

Two related types to know. NavigableMap and NavigableSet add navigation operations such as higherKey, lowerEntry, floorEntry and ceilingEntry — the queries you want when you are looking for the closest matching value rather than an exact one. And a TreeSet can be backed by a comparator, whereas its Map counterpart carries the comparator on the keys.