TreeMap<K, V> is an implementation of Java's Map interface that keeps its entries sorted by key. It is useful when an application needs more than key-based lookup: it may need to visit entries in order, find the nearest key to a given value, or retrieve a range of entries without sorting the entire map repeatedly.

Typical examples include:

• Displaying orders from the earliest date to the latest.
• Finding the highest or lowest score on a leaderboard.
• Finding the price tier at or just below a cart total.
• Retrieving orders whose timestamps fall within a particular interval.

Unlike HashMap, which does not guarantee iteration order, and LinkedHashMap, which maintains insertion or access order, TreeMap maintains key order. The trade-off is performance: its basic lookup and update operations are O(log n), whereas HashMap usually provides expected O(1) key lookup when hashes are well distributed.

2. How TreeMap Maintains Sorted Keys

TreeMap uses a red-black tree, a self-balancing binary search tree. Each node stores a key-value mapping and links to child nodes. The binary-search-tree property means that smaller keys belong on the left side and larger keys belong on the right side, according to the map's ordering rule.

A normal binary search tree can become badly unbalanced if keys arrive in an unfortunate order. A red-black tree maintains balancing properties so its height stays proportional to the logarithm of the number of entries. This is why TreeMap can offer logarithmic time for its main key-based operations.

The balancing rules themselves are implementation details. For everyday use, the key facts are that the tree stays balanced, entries are sorted by key, and core operations have logarithmic complexity.

3. TreeMap and the Map Interface

TreeMap implements Map and also supports the sorted-map and navigable-map capabilities. The ordinary Map methods work as expected:

The important difference is that iteration through the map's key, value, and entry views follows sorted key order. The order comes from the keys' natural ordering or from a comparator supplied when the map is constructed.

4. Natural Ordering and Custom Comparators

By default, TreeMap uses the natural ordering of its keys. For common types, this means:

• Integer, Long, and Double use numeric order.
• LocalDate uses chronological order.
• String uses lexicographic order.

ISO-formatted date strings such as 2026-05-10 sort chronologically under lexicographic ordering because the year, month, and day are arranged from most significant to least significant and consistently zero-padded.

If the desired order differs from natural ordering, pass a Comparator to the constructor. A comparator can define descending date order, case-insensitive string order, or ordering by a field of a custom class. The comparator must be consistent enough for the application to treat keys predictably; the map's ordering rule determines where keys are placed and how key equivalence is determined for map operations.

5. Basic Operations and Sorted Iteration

The core methods—put(), get(), remove(), containsKey(), and size()—work in the same general way as other map implementations. The visible difference appears during iteration.

Suppose date entries are inserted in this order: May 12, May 8, May 11, and May 9. Iterating over a TreeMap visits the dates in ascending key order rather than the order in which they were inserted.

This makes TreeMap useful for data that is naturally ordered. It also removes the need to copy keys to a separate list and sort them each time the application needs ordered output.

6. Endpoint Lookups: First and Last

The endpoint methods return the smallest or largest key, or the complete entry at that endpoint.

For example, if a leaderboard map uses scores as keys and player names as values, firstKey() returns the lowest score and lastKey() returns the highest score. The entry variants return the associated key and value together.

These operations can find an endpoint by following the leftmost or rightmost path through the tree rather than scanning every mapping. The time complexity is O(log n). If the map is empty, firstKey() and lastKey() throw NoSuchElementException; the entry-returning methods return null when no entry exists.

7. Neighbor Lookups: floorKey(), ceilingKey(), lowerKey(), and higherKey()

Navigation methods find the closest key relative to a supplied key. They are one of the main reasons to choose TreeMap.

The distinction is whether an exact match is allowed. floorKey(50) can return 50 if it exists; lowerKey(50) skips it and returns the next smaller key. Similarly, ceilingKey(50) can return 50, while higherKey(50) requires a strictly greater key.

Each method has an entry-returning counterpart such as floorEntry(), ceilingEntry(), lowerEntry(), and higherEntry(). These return a Map.Entry rather than only the key.

If no key satisfies the requested relationship, the navigation method returns null. Callers must handle this possibility, especially when the supplied key is below the minimum or above the maximum.

8. Practical Example: Price Tiers

Imagine a storefront where shipping fees are associated with lower bounds of price tiers. A TreeMap can store each tier boundary as a key and its shipping fee as the value.

When a cart total arrives, floorKey(total) finds the greatest tier boundary that does not exceed the total. The corresponding value gives the applicable fee, assuming the map contains a suitable starting boundary for all supported totals.

This is more direct than scanning every tier and manually tracking the largest boundary below the cart total. The map contains only the tier boundaries, so lookup cost depends on the number of boundaries, not on the number of possible cart totals.

Always consider the no-match case. If the cart total is smaller than the smallest configured tier boundary, floorKey() returns null, and the application needs an explicit fallback policy.

9. Range Views: headMap(), tailMap(), and subMap()

TreeMap can expose a range of entries through view methods. These methods are especially useful when data is keyed by dates, scores, prices, or other ordered values.

The common two-argument subMap(low, high) includes the lower bound and excludes the upper bound. For example, a date range from May 10 up to May 13 includes May 10, May 11, and May 12, but not May 13.

The NavigableMap API also offers overloads that allow each endpoint to be configured as inclusive or exclusive. These are useful when the range definition requires different boundary behavior.

10. Range Views Are Backed by the Original Map

The objects returned by headMap(), tailMap(), and subMap() are views, not independent copies. They reflect the corresponding portion of the original map.

This has two important consequences:

1. Changes made through the range view are reflected in the original map.
2. Changes to the original map within the range are reflected in the view.

For example, calling put() on a subMap is allowed when the new key is within that view's bounds. Trying to insert a key outside the permitted range throws IllegalArgumentException.

Range views are efficient to create because they record the bounds rather than copying every matching entry. Iterating over the view takes time proportional to the number of entries visited, plus the cost of finding the starting point.

11. Using TreeMap for Date and Time Ranges

A map keyed by comparable date or time values can be a natural fit for range queries. For example, an order history can be keyed by LocalDate or a timestamp. A range view can then expose orders within a chosen window in sorted order.

If keys are date strings, use a consistent sortable representation such as ISO format. If date objects are available, a date type such as LocalDate can express the ordering more clearly and avoid string-format mistakes.

Remember that the upper endpoint of the basic subMap(low, high) form is exclusive. Choose the appropriate overload when both endpoints must be included, and check the application’s intended boundary rules before processing the returned view.

12. Null Keys and Null Values

With natural ordering, TreeMap does not permit null keys. Inserting a key requires comparison with other keys, and natural ordering cannot compare null with ordinary key values. This generally results in a NullPointerException during insertion or another operation that requires the comparison.

A custom comparator could define a special position for null, but that behavior depends on the comparator. For ordinary natural ordering, treat null keys as unsupported.

Null values, however, are allowed. This creates the same ambiguity found in other maps that permit null values: get(key) returning null may mean the key is absent or that the key exists with a null value. Use containsKey(key) when the difference matters.

13. Thread Safety

TreeMap is not synchronized by default. If multiple threads access a shared instance and one or more threads modify it, the application must provide appropriate coordination.

For applications that need a sorted map with concurrent access, ConcurrentSkipListMap is a common alternative to consider. It provides concurrent sorted-map behavior, although its guarantees and performance characteristics differ from those of TreeMap.

Do not confuse sorted ordering with thread safety: keeping keys in order does not make simultaneous writes safe.

14. Performance and Complexity

HashMap usually has expected O(1) lookup for well-distributed keys, so it is often faster when only direct lookup is needed. TreeMap pays logarithmic operation costs to maintain sorted keys and provide navigation and range capabilities.

If data is loaded once and then read many times, it can sometimes be efficient to load it into a HashMap and sort a key list for a particular report. If data changes frequently and ordered operations are common, repeatedly sorting after each change can become more expensive than maintaining a TreeMap.

15. TreeMap vs HashMap vs LinkedHashMap vs Hashtable

TreeMap is the choice in this group when key order itself matters. LinkedHashMap remembers insertion or access order, which is different from sorting by key. HashMap remains the usual choice when ordering and navigation are unnecessary. Hashtable is a legacy class and is generally not the first choice for new code.

16. Common Mistakes

Mistake 1: Expecting constant-time lookup

TreeMap lookup is O(log n), not expected O(1). Its advantage is sorted order and navigation methods.

Mistake 2: Confusing insertion order with sorted order

LinkedHashMap follows insertion or access order. TreeMap follows key order.

Mistake 3: Forgetting the strict versus inclusive boundary

floorKey() and ceilingKey() allow equality; lowerKey() and higherKey() require a strict comparison.

Mistake 4: Forgetting that navigation can return null

If no key satisfies the requested relationship, the navigation method returns null. Always handle boundary cases.

Mistake 5: Treating a range view as a copy

Range views are backed by the original map. Updates can be visible from both directions, and inserting outside the view's bounds is not allowed.

Mistake 6: Assuming subMap(low, high) includes both endpoints

The basic two-key form includes the lower endpoint and excludes the upper endpoint. Use the inclusive/exclusive overload when needed.

Mistake 7: Using null keys with natural ordering

Natural ordering cannot compare null with ordinary keys. Avoid null keys unless a comparator explicitly defines and supports their ordering.

Mistake 8: Assuming TreeMap is thread-safe

Sorted order does not provide synchronization. Use appropriate coordination or consider a concurrent sorted map.

17. Best Practices

1. Use TreeMap when sorted key iteration or range queries are genuine requirements.
2. Prefer natural ordering for standard comparable types when it matches the required order.
3. Supply a comparator when the required order differs from natural ordering.
4. Use floorKey() for “at or below” lookups and ceilingKey() for “at or above” lookups.
5. Use lowerKey() and higherKey() when exact matches must be excluded.
6. Handle null returns from navigation methods.
7. Understand whether range endpoints are inclusive or exclusive.
8. Treat range views as live views rather than snapshots.
9. Avoid null keys with natural ordering.
10. Do not assume thread safety; coordinate shared access or choose a concurrent sorted-map implementation.
11. Use HashMap instead when only direct lookup is required and ordering adds no value.
12. Consider whether sorting a snapshot is more suitable for a one-off report than maintaining sorted order on every update.

18. Quick Revision

• TreeMap stores key-value pairs in sorted key order.
• It uses a self-balancing red-black tree.
• Basic lookup, insertion, and removal are O(log n).
• Natural ordering is used by default; a Comparator can customize it.
• firstKey() and lastKey() return the minimum and maximum keys.
• floorKey() returns the greatest key less than or equal to the input.
• ceilingKey() returns the smallest key greater than or equal to the input.
• lowerKey() and higherKey() require strict inequality.
• headMap(), tailMap(), and subMap() expose range views.
• Range views are backed by the original map.
• The basic subMap(low, high) includes the low endpoint and excludes the high endpoint.
• Natural ordering does not support null keys; null values are allowed.
• TreeMap is not synchronized by default.
• Choose TreeMap for key order and range operations, LinkedHashMap for encounter order, and HashMap for general unordered lookup.

19. Conclusion

TreeMap is especially valuable when keys are not merely identifiers but also define an order that the application needs to use. Its balanced tree keeps entries sorted and enables endpoint lookups, neighbor searches, and efficient range views.

Its logarithmic performance is the trade-off for maintaining order. For applications that need sorted dates, price tiers, leaderboards, or key-range processing, that trade is often worthwhile. For plain lookup without ordering needs, HashMap is generally the simpler default; for insertion order, LinkedHashMap is the better fit.