TreeMap is the Map implementation that keeps its entries sorted by key at all times. Unlike HashMap (no order) or LinkedHashMap (insertion order), TreeMap stores entries in a self-balancing binary search tree, so iterating its entries always walks them in key order, and a family of navigation methods like floorKey, ceilingKey, headMap, and subMap are available. This lesson covers how TreeMap is structured, how its key-based operations perform, the navigation methods that make it useful for range queries, and a few rough edges (like null keys) to watch for.

HashMap is great when the only requirement is looking up values by key. The keys are scattered across buckets in whatever order the hash function decides, which is usually fine, but breaks down the moment any of these is needed:

These are all key-ordered operations. A HashMap would force a copy of the keys into a list, a sort, and a walk. TreeMap keeps the keys ordered as they are inserted, so any of these operations is a direct method call.

Internally, TreeMap uses a Red-Black tree, which is a self-balancing binary search tree. The rebalancing rules don't matter here; the property that does is the cost of operations: get, put, remove, and containsKey are all O(log n). That's slower than HashMap's average O(1), but the trade gives guaranteed key order and the navigation methods.

The following picture shows what a TreeMap looks like internally after a few inserts. The keys are product prices used as price-tier markers:

The tree is roughly balanced. Every left subtree holds smaller keys, every right subtree holds larger keys, and the height stays close to log n. That's the property TreeMap relies on for all its operations.

TreeMap lookups are O(log n), not O(1). Without ordering needs and with well-hashed keys, HashMap is faster. Use TreeMap when sorted iteration or range queries are required.

TreeMap implements Map, so the everyday methods (put, get, remove, containsKey, size) work the same way they do on HashMap. The difference shows up only when iterating.

The dates came out sorted, even though they were inserted out of order. The same call on a HashMap would have printed entries in some arbitrary order; the same call on a LinkedHashMap would have walked them in insertion order. Only TreeMap walks them in key order, every time.

The default ordering for String is lexicographic, which matches ISO-format dates like these. For other types, the default is whatever the type's natural ordering says. Integer, Long, and Double sort numerically; LocalDate sorts chronologically. For a different order (descending dates, case-insensitive strings, sort by a field of a custom class), pass a Comparator to the constructor. Natural ordering is used throughout this lesson.

The navigation methods are the main reason to use TreeMap. They answer questions like "what's the key just before X?", "what's the smallest key in this range?", or "what's the view of every entry between two endpoints?" without scanning the whole map.

The full set splits into three groups: endpoint lookups, neighbor lookups, and range views.

Endpoint Lookups

firstKey() and lastKey() return the smallest and largest keys. firstEntry() and lastEntry() return the whole Map.Entry (key plus value) for the same positions.

The keys are Integer scores, so natural ordering is numeric. firstKey() is the minimum (1450), lastKey() is the maximum (2100), and the entry forms hand back the corresponding name in one call. On a HashMap, the same result requires walking every entry and tracking the min/max manually.

firstKey, lastKey, firstEntry, and lastEntry are O(log n). The tree descends straight down the left or right spine; it doesn't scan the whole map.

Neighbor Lookups

Four methods find the key "near" a given value:

The difference between floor and lower is the equals case. floorKey(50) will return 50 if it's a key in the map; lowerKey(50) will skip past it and find the next key down. Same idea for ceiling versus higher, in the upward direction.

A common use case is price tiers. A storefront has shipping fees attached to price brackets, stored as a TreeMap keyed by the bracket's lower bound. When a cart total comes in, floorKey finds the bracket it falls into:

Every cart total finds its bracket in one floorKey call. The map only stores the bracket boundaries (four entries), so the lookup is cheap regardless of how many possible cart totals exist.

The picture below shows the same map and what each navigation method returns when asked about the input 50.0:

floorKey(50.0) and ceilingKey(50.0) both return 50.0 because the input is an exact match. lowerKey(50.0) skips it and returns the next key down (25.0); higherKey(50.0) skips it and returns the next key up (100.0). Each method also has an Entry variant (floorEntry, ceilingEntry, and so on) that returns the whole entry instead of just the key.

If no key satisfies the request, every navigation method returns null. For example, lowerKey(0.0) returns null because nothing in the map is strictly less than the smallest key. Code that uses these methods has to handle that case.

Every navigation lookup is O(log n). The tree descends from the root, comparing the input against each node's key until it finds the answer or runs off the end.

Range Views

headMap, tailMap, and subMap return a view of a slice of the map. The view is backed by the original TreeMap, so it's not a copy; changes to the view show up in the original, and vice versa.

A useful application is fetching all orders within a date range. The TreeMap is keyed by date string, and subMap returns just the slice for the requested window:

subMap("2026-05-10", "2026-05-13") returns a view of entries from the 10th up to (but not including) the 13th. Three entries match, and walking the view's entrySet() gives them in key order, the same way iterating the parent map would. The 13th itself is excluded because subMap is half-open: low is inclusive, high is exclusive. This matches how slices work in most other places in Java, like String.substring(int, int).

To make both endpoints inclusive (or both exclusive), there's an overload subMap(low, lowInclusive, high, highInclusive) on NavigableMap. The simpler three-argument form above is the most common.

headMap("2026-05-10") would return {2026-05-08, 2026-05-09} (everything strictly before the 10th). tailMap("2026-05-11") would return {2026-05-11, 2026-05-12, 2026-05-13} (the 11th onward). Because the views are live, calling put on them is also valid as long as the new key falls within the view's bounds. Inserting outside the bounds throws IllegalArgumentException.

Range views are O(1) to create. They don't copy entries, they just remember the bounds. Iterating a view is O(k) where k is the number of entries inside the bounds.

TreeMap doesn't allow null keys when using natural ordering. Inserting a key requires comparing it against existing keys, and null.compareTo(anything) throws NullPointerException. Java surfaces that failure at the put, not later when the map is read.

The first put succeeds because there's nothing to compare against yet. The second one fails because Java tries to compare null to "Notebook" to decide where in the tree it goes. With a custom Comparator that handles null (most don't), the behavior would depend on the comparator, but for natural ordering, null is forbidden.

null values, on the other hand, are allowed:

The entry exists with a null value, which is why containsKey("Pen") returns true. Code that reads the value has to distinguish between "no entry for this key" and "entry exists, value is null", because both get calls return null. Use containsKey when that distinction matters.

One other detail: TreeMap is not synchronized. Concurrent reads are fine, but if any thread modifies the map while another iterates or modifies it, the behavior is undefined. For thread-safe sorted maps, see ConcurrentSkipListMap.

HashMap is the default Map. Use TreeMap when at least one of these is true:

If none of those apply and only get/put performance matters, stay with HashMap. A TreeMap lookup is O(log n) versus HashMap's average O(1), and even at moderate sizes the constant factor difference adds up.

For sorted order without the navigation methods, when the data is loaded once and read many times, sorting a HashMap's key set into a list is sometimes cheaper than maintaining a TreeMap. But when the data changes over time, the bookkeeping cost of re-sorting on every write will dwarf the TreeMap's O(log n) overhead.

Here's a quick comparison of the four Map implementations:

TreeMap is the only one in this group that offers ordering by key. Insertion order is different (and is LinkedHashMap's job). When the application cares about key order or wants range queries, use TreeMap.