Java TreeMap
A TreeMap is Java’s sorted implementation of the Map interface: it stores key-value pairs and automatically keeps the keys in ascending order (or a custom order you supply) at all times. Unlike a HashMap, which gives you fast but unordered access, TreeMap trades a small amount of speed for guaranteed ordering and powerful navigation operations. That makes it the right tool whenever you need a map that behaves like a sorted dictionary — leaderboards, price ranges, scheduling by timestamp, or any lookup where “give me everything between X and Y” matters.
Overview: How TreeMap Works
TreeMap is part of the Java Collections Framework and implements the NavigableMap interface, which extends SortedMap, which extends Map. Internally, a TreeMap is backed by a red-black tree — a self-balancing binary search tree. Every time you insert or remove a key, the tree rebalances itself (through rotations and recoloring of nodes) so that no path from the root to a leaf is ever more than roughly twice as long as any other path. This guarantee is what keeps operations fast and predictable.
Because the underlying structure is a binary search tree, every key must be comparable to every other key. When you don’t supply a Comparator, TreeMap uses the keys’ natural ordering via the Comparable interface — this is why String, Integer, Double, and other built-in types work out of the box (they all implement Comparable). If you want a custom order (descending, by length, by a secondary field), you pass a Comparator to the constructor, and the TreeMap uses that instead of compareTo for every comparison, including equality checks for duplicate keys.
Core operations — put, get, remove, containsKey — all run in O(log n) time, because each one is essentially a binary search down the tree, followed by a rebalance on insert/remove. Compare this to HashMap‘s average O(1), and you can see the trade-off: TreeMap is slower per operation but rewards you with sorted iteration and range queries that a hash table simply cannot offer efficiently. Iterating a TreeMap (via keySet(), values(), or entrySet()) always visits keys in sorted order — this is a guarantee, not an implementation detail you’re relying on.
TreeMap also implements NavigableMap, which adds a rich set of methods for finding neighboring keys: floorKey, ceilingKey, higherKey, lowerKey, plus range views like headMap, tailMap, and subMap. These are backed directly by tree traversal, so they are also O(log n) — far better than manually filtering and sorting a HashMap‘s entries every time you need a range.
One important restriction: TreeMap does not allow a null key, because the tree must be able to compare every key against every other key, and comparing against null is undefined (it throws a NullPointerException). null values, however, are allowed. TreeMap is also not thread-safe; for concurrent sorted access, use ConcurrentSkipListMap instead.
Syntax
TreeMap<K, V> map = new TreeMap<>(); // natural ordering
TreeMap<K, V> map = new TreeMap<>(Comparator<K> cmp); // custom ordering
TreeMap<K, V> map = new TreeMap<>(Map<K, V> other); // copy from another map
TreeMap<K, V> map = new TreeMap<>(SortedMap<K, V> other); // copy, keeping its comparator- K — the key type; must implement
Comparable<K>unless aComparatoris supplied. - V — the value type; no restrictions.
- Comparator<K> — an optional ordering rule; if omitted, natural ordering (
compareTo) is used.
| Method | Purpose |
|---|---|
put(K key, V value) |
Insert or update a key-value pair |
get(Object key) |
Retrieve the value for a key, or null |
firstKey() / lastKey() |
Smallest / largest key currently in the map |
floorKey(K key) / ceilingKey(K key) |
Largest key ≤ given key / smallest key ≥ given key |
lowerKey(K key) / higherKey(K key) |
Largest key < given key / smallest key > given key |
headMap(K toKey) |
View of entries strictly less than toKey |
tailMap(K fromKey) |
View of entries greater than or equal to fromKey |
subMap(K from, K to) |
View of entries from from (inclusive) to to (exclusive) |
pollFirstEntry() / pollLastEntry() |
Remove and return the smallest / largest entry |
Examples
Example 1: Basic Insertion and Sorted Iteration
import java.util.TreeMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
TreeMap<String, Integer> ages = new TreeMap<>();
ages.put("Charlie", 35);
ages.put("Alice", 28);
ages.put("Bob", 42);
ages.put("Diana", 31);
for (Map.Entry<String, Integer> entry : ages.entrySet()) {
System.out.println(entry.getKey() + " -> " + entry.getValue());
}
}
}Output:
Alice -> 28
Bob -> 42
Charlie -> 35
Diana -> 31Even though the entries were inserted in the order Charlie, Alice, Bob, Diana, the TreeMap stores and iterates them alphabetically, because String‘s natural ordering (lexicographic comparison) is used automatically.
Example 2: Custom Ordering with a Comparator
import java.util.TreeMap;
import java.util.Comparator;
public class Main {
public static void main(String[] args) {
TreeMap<Integer, String> scores = new TreeMap<>(Comparator.reverseOrder());
scores.put(85, "Alice");
scores.put(92, "Bob");
scores.put(78, "Charlie");
scores.put(95, "Diana");
System.out.println("Leaderboard (highest first):");
for (Integer score : scores.keySet()) {
System.out.println(score + " - " + scores.get(score));
}
}
}Output:
Leaderboard (highest first):
95 - Diana
92 - Bob
85 - Alice
78 - CharliePassing Comparator.reverseOrder() to the constructor tells the tree to order keys from highest to lowest instead of using Integer‘s natural ascending order. Every internal comparison — insertion, lookup, iteration — now uses this comparator instead of compareTo.
Example 3: Navigation Methods on a Real Range Query
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
TreeMap<Integer, String> inventory = new TreeMap<>();
inventory.put(101, "Widget");
inventory.put(205, "Gadget");
inventory.put(150, "Gizmo");
inventory.put(310, "Doohickey");
System.out.println("First key: " + inventory.firstKey());
System.out.println("Last key: " + inventory.lastKey());
System.out.println("Ceiling of 160: " + inventory.ceilingKey(160));
System.out.println("Floor of 160: " + inventory.floorKey(160));
System.out.println("Higher than 150: " + inventory.higherKey(150));
System.out.println("Lower than 150: " + inventory.lowerKey(150));
System.out.println("HeadMap(205): " + inventory.headMap(205));
System.out.println("TailMap(150): " + inventory.tailMap(150));
}
}Output:
First key: 101
Last key: 310
Ceiling of 160: 205
Floor of 160: 150
Higher than 150: 205
Lower than 150: 101
HeadMap(205): {101=Widget, 150=Gizmo}
TailMap(150): {150=Gizmo, 205=Gadget, 310=Doohickey}This is where TreeMap truly earns its keep. ceilingKey(160) finds the smallest stored key that is at least 160 (205), while floorKey(160) finds the largest key at most 160 (150). headMap and tailMap return live views of the map restricted to a range — useful for tasks like “find the next available time slot” or “get all product IDs below a threshold” without writing a manual search loop.
Under the Hood: What Happens on put() and get()
When you call map.put(key, value), the TreeMap walks down the red-black tree starting at the root, comparing your key to each node’s key using compareTo (or your Comparator). It goes left when the new key is smaller and right when it’s larger, until it finds an empty spot or an existing node with an equal key (which it then overwrites). After inserting a new node, the tree checks red-black properties (no two red nodes in a row, equal black-height on every path) and performs rotations and recoloring as needed to restore balance — this is what keeps the tree from degenerating into a slow linked list even under adversarial insertion orders.
get(key) performs the same downward comparison walk without any rebalancing, so it’s a pure O(log n) binary search. Because the tree height is kept at O(log n) by the balancing algorithm, both operations scale gracefully even with millions of entries. Iteration (entrySet(), keySet()) performs an in-order traversal of the tree (left subtree, node, right subtree), which is precisely what produces sorted output — it isn’t a separate sort step, it’s a direct consequence of how binary search trees are structured.
Common Mistakes
Mistake 1: Using a Custom Key Class Without Comparable or a Comparator
class Point {
int x, y;
Point(int x, int y) { this.x = x; this.y = y; }
}
TreeMap<Point, String> map = new TreeMap<>();
map.put(new Point(1, 2), "A");
map.put(new Point(3, 4), "B"); // throws ClassCastException at runtimeThis compiles fine because generics don’t check for Comparable at compile time when no Comparator is given. But as soon as the tree needs to compare two Point keys to decide where the second one belongs, it tries to cast Point to Comparable and fails, throwing a ClassCastException. Fix it by either implementing Comparable<Point> on the class or supplying a Comparator<Point> to the constructor:
import java.util.TreeMap;
import java.util.Comparator;
class Point {
int x, y;
Point(int x, int y) { this.x = x; this.y = y; }
public String toString() { return "(" + x + "," + y + ")"; }
}
public class Main {
public static void main(String[] args) {
TreeMap<Point, String> map = new TreeMap<>(
Comparator.<Point>comparingInt(p -> p.x).thenComparingInt(p -> p.y));
map.put(new Point(3, 4), "B");
map.put(new Point(1, 2), "A");
System.out.println(map);
}
}Mistake 2: Assuming null Keys Work Like They Do in HashMap
TreeMap<String, Integer> map = new TreeMap<>();
map.put(null, 1); // throws NullPointerExceptionHashMap happily accepts one null key, which leads many developers to assume every map does. TreeMap cannot: it must be able to compare the new key against existing keys to place it in the tree, and comparing null makes no sense, so it throws immediately. If you need a placeholder for “no key,” use a sentinel value or an Optional-wrapped key type instead of null.
Best Practices
- Use
TreeMaponly when you actually need sorted order or range queries — if you just need fast lookups,HashMapis faster forput/get. - Prefer immutable keys. If a key’s fields change after insertion in a way that affects
compareTo, the tree’s internal ordering becomes corrupted and lookups silently fail. - When natural ordering isn’t what you want, pass a
Comparatorto the constructor rather than wrapping keys in a helper class. - Use
floorEntry/ceilingEntry/subMapinstead of manually filtering and sorting entries when you need a range — they’re O(log n) and far cleaner. - Remember that
headMap,tailMap, andsubMapreturn live views backed by the original map; modifying the view modifies the underlyingTreeMap. - Never rely on a mutable
Comparatorwhose comparison logic can change after the map is built — it breaks the tree’s invariants. - If you need thread safety with sorted order, use
ConcurrentSkipListMaprather than wrapping aTreeMapinCollections.synchronizedSortedMapfor high-contention use cases.
Practice Exercises
- Exercise 1: Create a
TreeMap<String, Double>of product names to prices. Insert at least five products, then print the cheapest and most expensive product usingfirstEntry()andlastEntry(). - Exercise 2: Build a
TreeMap<Integer, String>mapping exam scores to student names. Given a passing threshold of 60, usetailMap(60)to print only the students who passed, in ascending score order. - Exercise 3: Write a program that stores event timestamps (as
Integerminutes since midnight) as keys in aTreeMap<Integer, String>. Given a target time, usefloorKeyandceilingKeyto print the nearest event before and after that time.
Summary
TreeMapis aNavigableMapbacked by a self-balancing red-black tree, keeping keys always in sorted order.- Keys must implement
Comparable, or you must supply aComparator— otherwise aClassCastExceptionoccurs the moment two incomparable keys need to be compared. - Core operations (
put,get,remove) run in O(log n) time, slower thanHashMap‘s average O(1) but with guaranteed ordering. - Navigation methods like
floorKey,ceilingKey,headMap, andtailMapmake range queries fast and simple. TreeMapdoes not allownullkeys and is not thread-safe.- Use it whenever sorted iteration or range-based lookups matter more than raw insertion/lookup speed.
