TreeMap

TreeMap<K, V> is Java’s go-to Map when you need your key-value pairs kept in sorted key order at all times. Every put, get, and remove runs in O(log n) time — and you gain powerful navigation methods like “give me all keys less than X” for free.

What is TreeMap?

TreeMap<K, V> lives in java.util and implements NavigableMap<K, V>, which extends SortedMap<K, V> and then Map<K, V>. Internally it is backed by a red-black tree — a self-balancing binary search tree that guarantees O(log n) performance for all structural operations.

Key characteristics at a glance:

Feature	Detail
Duplicate keys	Not allowed (duplicate value is overwritten)
Null keys	Not permitted — throws NullPointerException
Null values	Allowed
Order	Sorted by key — natural ordering or a custom Comparator
Thread safety	Not synchronized
Time complexity	O(log n) for put / get / remove

Note: Natural ordering is defined by the Comparable implementation of the key type. String sorts lexicographically, Integer sorts numerically. See Comparable for the full picture.

Creating a TreeMap

import java.util.TreeMap;

public class BasicTreeMap {
    public static void main(String[] args) {
        TreeMap<String, Integer> population = new TreeMap<>();
        population.put("Toronto",  2_930_000);
        population.put("Montreal", 2_110_000);
        population.put("Calgary",    820_000);
        population.put("Ottawa",     994_000);

        System.out.println(population);
    }
}

Output:

{Calgary=820000, Montreal=2110000, Ottawa=994000, Toronto=2930000}

Keys are printed in ascending alphabetical order automatically — no manual sorting required.

Constructors

// Natural ordering (keys must implement Comparable)
TreeMap<String, Integer> map1 = new TreeMap<>();

// Custom ordering via a Comparator (reverse alphabetical)
TreeMap<String, Integer> map2 = new TreeMap<>(Comparator.reverseOrder());

// Copy from another Map (preserves natural ordering)
TreeMap<String, Integer> map3 = new TreeMap<>(map1);

// Copy from a SortedMap, retaining its Comparator
TreeMap<String, Integer> map4 = new TreeMap<>(map1);

Common Operations

Adding and Accessing Entries

import java.util.TreeMap;

public class TreeMapOps {
    public static void main(String[] args) {
        TreeMap<Integer, String> grades = new TreeMap<>();
        grades.put(3, "Junior");
        grades.put(1, "Freshman");
        grades.put(4, "Senior");
        grades.put(2, "Sophomore");

        // Access by key
        System.out.println(grades.get(2));          // Sophomore

        // Default value if key absent
        System.out.println(grades.getOrDefault(5, "Graduate")); // Graduate

        // Check presence
        System.out.println(grades.containsKey(3));  // true
        System.out.println(grades.containsValue("Senior")); // true
    }
}

Output:

Sophomore
Graduate
true
true

Removing Entries

grades.remove(1);                        // remove by key
grades.remove(4, "Senior");              // conditional remove (key + value match)

Iterating

import java.util.TreeMap;

public class TreeMapIterate {
    public static void main(String[] args) {
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("Zara", 88);
        scores.put("Alex", 95);
        scores.put("Mike", 79);

        // Entry set — sorted by key
        for (var entry : scores.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

Output:

Alex -> 95
Mike -> 79
Zara -> 88

Tip: You can also iterate using keySet() for just keys, or values() for just values. Both respect sorted order.

NavigableMap Methods

This is where TreeMap really shines over HashMap. NavigableMap gives you rich “floor/ceiling/range” navigation that no other standard Map offers.

First and Last Keys

TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(10, "ten"); tm.put(30, "thirty");
tm.put(20, "twenty"); tm.put(50, "fifty");

System.out.println(tm.firstKey());  // 10
System.out.println(tm.lastKey());   // 50
System.out.println(tm.firstEntry()); // 10=ten
System.out.println(tm.lastEntry());  // 50=fifty

Floor, Ceiling, Lower, Higher

// floorKey(k)   — greatest key <= k
System.out.println(tm.floorKey(25));    // 20

// ceilingKey(k) — smallest key >= k
System.out.println(tm.ceilingKey(25));  // 30

// lowerKey(k)   — greatest key strictly < k
System.out.println(tm.lowerKey(30));    // 20

// higherKey(k)  — smallest key strictly > k
System.out.println(tm.higherKey(20));   // 30

SubMap, HeadMap, TailMap

// subMap — keys in range [fromKey, toKey)
System.out.println(tm.subMap(10, 40));  // {10=ten, 20=twenty, 30=thirty}

// headMap — keys strictly less than toKey
System.out.println(tm.headMap(30));     // {10=ten, 20=twenty}

// tailMap — keys >= fromKey
System.out.println(tm.tailMap(20));     // {20=twenty, 30=thirty, 50=fifty}

Note: The range views returned by subMap, headMap, and tailMap are live — changes to the view affect the backing TreeMap and vice versa. Use subMap(from, true, to, true) for inclusive bounds on both ends.

Polling (Removing) the Extremes

// Remove and return the entry with the smallest key
Map.Entry<Integer, String> min = tm.pollFirstEntry(); // {10=ten}

// Remove and return the entry with the largest key
Map.Entry<Integer, String> max = tm.pollLastEntry();  // {50=fifty}

These are useful for priority-queue-style processing where you always want the smallest or largest item.

Custom Ordering with a Comparator

If natural ordering does not fit your needs, pass a Comparator to the constructor:

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

public class ReverseTreeMap {
    public static void main(String[] args) {
        // Keys sorted in descending order
        TreeMap<String, Integer> desc = new TreeMap<>(Comparator.reverseOrder());
        desc.put("Banana", 3);
        desc.put("Apple",  7);
        desc.put("Cherry", 1);

        System.out.println(desc);
    }
}

Output:

{Cherry=1, Banana=3, Apple=7}

Warning: If you provide a Comparator, the map’s notion of “equal” for keys comes from that comparator, not from equals(). Two keys that compare to 0 are treated as the same key, even if equals() says otherwise.

TreeMap vs HashMap vs LinkedHashMap

	TreeMap	HashMap	LinkedHashMap
Order	Sorted by key	No order	Insertion order
Null keys	No	Yes (one)	Yes (one)
Performance	O(log n)	O(1) average	O(1) average
NavigableMap	Yes	No	No
Best for	Range queries, sorted output	General-purpose lookup	Predictable iteration

See HashMap vs Hashtable and LinkedHashMap for more comparison details.

Under the Hood

Red-Black Tree

TreeMap is backed by a red-black tree — a self-balancing binary search tree. Each node stores a key, a value, pointers to left/right children and parent, and a color bit (red or black). The balancing invariants guarantee that the longest path from root to leaf is no more than twice the shortest path, which keeps the tree height at O(log n) for n entries.

Whenever you call put() or remove(), the tree may perform rotations and recoloring to maintain balance. This is why writes have an O(log n) floor that can never be optimized away — unlike HashMap’s amortized O(1).

Comparator vs. Comparable

When you call put(key, value), TreeMap finds the insertion point by calling either:

• compareTo() on the key (natural ordering via Comparable), or
• the Comparator you supplied at construction time.

There is no use of hashCode() or equals() for key location — this is purely comparison-based. A consequence: a class that has equals() but no Comparable (or no Comparator) will throw a ClassCastException at runtime.

Memory Layout

Each node in the tree is a java.util.TreeMap.Entry<K, V> object with six fields: key, value, left, right, parent, and color. For n entries you have exactly n Entry objects on the heap — no backing array, no load-factor resizing. This makes TreeMap more memory-predictable than HashMap, but each entry carries more overhead than a raw array slot.

Thread Safety

TreeMap is not thread-safe. For concurrent sorted access, use Collections.synchronizedSortedMap(new TreeMap<>()) or — for higher concurrency — ConcurrentSkipListMap from java.util.concurrent. See Concurrent Collections for details.

Practical Example — Word Frequency in Sorted Order

import java.util.TreeMap;

public class WordFrequency {
    public static void main(String[] args) {
        String sentence = "the quick brown fox jumps over the lazy dog the fox";
        TreeMap<String, Integer> freq = new TreeMap<>();

        for (String word : sentence.split(" ")) {
            freq.merge(word, 1, Integer::sum);
        }

        // Already sorted alphabetically
        freq.forEach((word, count) ->
            System.out.printf("%-8s : %d%n", word, count));
    }
}

Output:

brown    : 1
dog      : 1
fox      : 2
jumps    : 1
lazy     : 1
over     : 1
quick    : 1
the      : 3

Tip: Map.merge(key, 1, Integer::sum) is the cleanest idiom for counting — it inserts 1 on the first occurrence and adds 1 on every subsequent one. No if (containsKey(...)) required.

Related Topics

• HashMap — the fastest general-purpose Map when sorted order is not needed
• LinkedHashMap — preserves insertion order without the O(log n) cost
• TreeSet — a sorted Set that is backed by a TreeMap internally
• Comparator — define custom sort orders for TreeMap keys
• Map Interface — the contract all Map implementations follow
• Concurrent Collections — thread-safe sorted maps for multi-threaded code