TreeMap

A TreeMap is a map that keeps its entries sorted by key. It supports everything a HashMap does (put, get, remove, iterate) but always iterates in key order and adds methods that depend on that order: the smallest or largest key, the nearest key to a given value, and views of key ranges. It is implemented as a red-black tree, so its main operations take O(log n) time.

Creating and Using a TreeMap

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

TreeMap<String, Integer> branches = new TreeMap<>();
branches.put("mumbai", 3);
branches.put("chennai", 5);
branches.put("pune", 1);
branches.put("delhi", 2);

System.out.println(branches);   // {chennai=5, delhi=2, mumbai=3, pune=1}

The keys come out in alphabetical order regardless of insertion order. The usual map methods (get, put, remove, containsKey, getOrDefault, merge, computeIfAbsent, and so on) behave exactly as described in the HashMap lesson.

Key Ordering

Keys are ordered by their natural ordering (they must implement Comparable) or by a Comparator passed to the constructor:

TreeMap<String, Integer> caseInsensitive = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitive.put("Java", 1);
caseInsensitive.put("java", 2);          // same key under this comparator: replaces the value
System.out.println(caseInsensitive);     // {Java=2}

TreeMap<Integer, String> descending = new TreeMap<>(Comparator.reverseOrder());
descending.putAll(Map.of(1, "one", 3, "three", 2, "two"));
System.out.println(descending);          // {3=three, 2=two, 1=one}

As with TreeSet, keys are considered equal when the comparison returns 0. equals and hashCode are not used. In the first example, "Java" and "java" count as the same key, so the second put replaces the value but keeps the original key.

Keys without a natural ordering and no comparator cause ClassCastException on the first put. A null key is not allowed with natural ordering; null values are allowed.

Navigation Methods

TreeMap implements NavigableMap. Using the map above, {chennai=5, delhi=2, mumbai=3, pune=1}:

The navigation methods return null when no such key exists. firstKey and lastKey throw NoSuchElementException on an empty map, while firstEntry and lastEntry return null.

floorEntry is the key to many real problems: "which price band does this amount fall into?", "which configuration version was active at this time?", "which tax slab applies to this income?". The answer is the entry with the greatest key not exceeding the value.

Range Views

branches.headMap("mumbai");           // {chennai=5, delhi=2}          keys < "mumbai"
branches.tailMap("mumbai");           // {mumbai=3, pune=1}            keys ≥ "mumbai"
branches.subMap("d", "p");            // {delhi=2, mumbai=3}           "d" ≤ key < "p"
branches.headMap("mumbai", true);     // {chennai=5, delhi=2, mumbai=3}
branches.descendingMap();             // {pune=1, mumbai=3, delhi=2, chennai=5}
branches.navigableKeySet();           // sorted view of the keys

The same conventions as TreeSet apply: the lower bound is inclusive and the upper bound exclusive by default, and overloads with boolean flags control each end. These are live views: they reflect later changes to the map, and modifications through a view update the map.

Iterating

Iteration over keySet(), values(), entrySet(), or forEach always follows key order:

TreeMap<LocalDate, Double> dailySales = new TreeMap<>();
dailySales.put(LocalDate.of(2026, 11, 3), 18_400.0);
dailySales.put(LocalDate.of(2026, 11, 1), 12_250.0);
dailySales.put(LocalDate.of(2026, 11, 2), 9_800.0);

dailySales.forEach((date, amount) -> System.out.println(date + "  " + amount));

Output:

2026-11-01  12250.0
2026-11-02  9800.0
2026-11-03  18400.0

LocalDate keys sort chronologically, which makes TreeMap a natural fit for time-series data: daily totals, price histories, event logs.

Performance

Use TreeMap when you need sorted keys or nearest-key lookups. When you only need fast lookups by exact key, HashMap is faster.

Common Uses

Counting with sorted output

TreeMap<String, Integer> wordCount = new TreeMap<>();
for (String w : "the cat and the hat and the bat".split(" ")) {
    wordCount.merge(w, 1, Integer::sum);
}
System.out.println(wordCount);   // {and=2, bat=1, cat=1, hat=1, the=3}

The result is alphabetized automatically, with no separate sorting step.

Leaderboards and top-N

With a reverse-order comparator, the highest keys come first, and pollFirstEntry removes the current leader:

TreeMap<Integer, String> board = new TreeMap<>(Comparator.reverseOrder());
board.put(820, "ada");
board.put(910, "linus");
board.put(760, "grace");
System.out.println(board.firstEntry());   // 910=linus

Note that each score can appear only once as a key. When several players can share a score, use TreeMap<Integer, List<String>> with computeIfAbsent.

Range-based lookups

The practical example below uses floorEntry, headMap, and higherKey to compute a slab-based electricity bill.

TreeMap Versus HashMap Versus LinkedHashMap

Practical Example: Slab-Based Electricity Tariff

A utility charges per unit at increasing rates as consumption crosses slab boundaries. Each slab starts at a number of units, and the rate applies to units from that point up to the next slab's start. (The rates below are illustrative.)

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

public class Tariff {
    // slab start (units) -> rate per unit for units from that start upward
    static final NavigableMap<Integer, Double> RATES = new TreeMap<>(Map.of(
        0, 0.0,
        100, 2.35,
        200, 4.70,
        400, 6.30,
        500, 8.40
    ));

    static double bill(int units) {
        double total = 0;
        for (Map.Entry<Integer, Double> slab : RATES.headMap(units, false).entrySet()) {
            int start = slab.getKey();
            Integer nextStart = RATES.higherKey(start);
            int end = (nextStart == null) ? units : Math.min(units, nextStart);
            total += (end - start) * slab.getValue();
        }
        return total;
    }

    public static void main(String[] args) {
        for (int units : new int[]{80, 150, 450, 620}) {
            double rate = RATES.floorEntry(units).getValue();
            System.out.printf("%4d units: bill %8.2f, marginal rate %.2f%n", units, bill(units), rate);
        }
        System.out.println("Slabs above 200: " + RATES.tailMap(200, false));
    }
}

Output:

  80 units: bill     0.00, marginal rate 0.00
 150 units: bill   117.50, marginal rate 2.35
 450 units: bill  1490.00, marginal rate 6.30
 620 units: bill  2813.00, marginal rate 8.40
Slabs above 200: {400=6.3, 500=8.4}

The TreeMap holds slab start points in order. floorEntry(units) finds the slab containing the last unit consumed, giving the marginal rate in a single O(log n) call. bill iterates only over the slabs that begin below the consumption (headMap(units, false)), and higherKey finds where each slab ends. For 450 units: 100 units at 2.35, 200 units at 4.70, and 50 units at 6.30, totalling 1,490. Map.of provides the data unordered; wrapping it in a TreeMap sorts the keys, so adding a new slab requires no other code changes.