Java With Us

<code>TreeMap</code> in Java — Sorted Map (Red-Black Tree)

Updated on 2026-04-21 Reviewed by the Java With Us editorial team

TreeMap is a sorted Map backed by a red-black tree. Keys are kept in order (natural or by a Comparator) — get, put, remove are all O(log n). The sorted structure gives you range queries: "give me every entry between these two keys".

Basics

var ranks = new TreeMap<String, Integer>();
ranks.put("Bob",   2);
ranks.put("Alice", 1);
ranks.put("Carol", 3);

ranks.firstKey();       // "Alice" — smallest key
ranks.lastKey();        // "Carol"
ranks.forEach((k, v) -> System.out.println(k));   // Alice, Bob, Carol — sorted

Navigation methods

var scores = new TreeMap<>(Map.of(
    "alice", 90, "bob", 72, "carol", 85, "dave", 60));

scores.floorKey("b");          // "alice" — largest key ≤ "b"
scores.ceilingKey("b");        // "bob"   — smallest key ≥ "b"
scores.higherKey("bob");       // "carol" — strictly >
scores.lowerKey("carol");      // "bob"   — strictly <
scores.headMap("carol");       // {alice=90, bob=72} — all keys < "carol"
scores.tailMap("bob");         // from "bob" inclusive
scores.subMap("bob", "dave");  // ["bob", "dave") half-open range

Custom order

var byLengthDesc = new TreeMap<String, Integer>(
    Comparator.comparingInt(String::length).reversed()
);
byLengthDesc.put("a", 1);
byLengthDesc.put("ccc", 3);
byLengthDesc.put("bb", 2);
// iterates "ccc", "bb", "a"

Performance — when TreeMap wins

  • You need range queries (subMap, headMap, tailMap).
  • You need to iterate in sorted order repeatedly without paying the sort cost each time.
  • You need floor/ceiling lookups on a continuous key space (timestamps, version numbers).

If you just want sorted iteration once, HashMap + stream().sorted() is fine — and O(n log n) is faster than maintaining O(log n) per operation if lookups are rare.

Common mistakes

  • Keys that aren't Comparable — you'll get a ClassCastException at runtime. Pass a Comparator explicitly.
  • Mutable keys — if sorting order depends on a field that changes, the tree is corrupted.
  • Using TreeMap by default — O(log n) is slower than HashMap's O(1) for the common lookup case. Only pick TreeMap if you need ordering.

Related

Pillar: Java collections. Siblings: HashMap, TreeSet.

Related articles