Java TreeMap and TreeSet Explained — Sorted, Navigable, and Powerful
Every non-trivial Java application eventually needs sorted data — a leaderboard ranked by score, a task scheduler ordered by deadline, a word-frequency map listed alphabetically. You could dump everything into an ArrayList and call Collections.sort() every time, but that's like re-alphabetising your entire library every time a new book arrives. Java's TreeMap and TreeSet solve this permanently by keeping data sorted at all times, automatically, on every insert and delete.
The problem with HashMap and HashSet is that they trade order for raw speed. That's a great deal when you only need to answer 'does this key exist?' or 'give me this value'. But the moment a user asks 'show me the top 10 scores' or 'find everything between Tuesday and Friday', a HashMap forces you to scan the entire structure. A TreeMap answers those range and boundary questions in O(log n) time because it's backed by a Red-Black Tree — a self-balancing binary search tree that keeps everything sorted without you lifting a finger.
By the end of this article you'll know exactly when to reach for a TreeMap versus a HashMap, how to exploit the NavigableMap and NavigableSet APIs to slice your data in powerful ways, and which subtle mistakes cause ClassCastExceptions and incorrect ordering in production. You'll also have concrete, real-world patterns you can copy directly into your own codebase.
TreeSet — When Order Is Non-Negotiable
A TreeSet is a Set — so it never stores duplicates — but unlike HashSet it keeps every element in its natural sorted order at all times. 'Natural order' means whatever Comparable defines for that type: alphabetical for Strings, ascending for numbers, chronological for dates.
The real payoff isn't just iteration order. It's the NavigableSet API: methods like first(), last(), floor(), ceiling(), headSet(), and tailSet() let you slice and query your sorted data without loops. Want every username that comes after 'mike' alphabetically? One line. Want the five closest scores below a threshold? One line.
Internally, TreeSet wraps a TreeMap and stores your elements as keys. Every add(), remove(), and contains() runs in O(log n) — slower than HashSet's O(1) average, but a fair trade when you genuinely need sorted access. Don't use TreeSet by default; use it when the ordering itself is part of the feature you're building.
import java.util.TreeSet; import java.util.NavigableSet; public class LeaderboardTreeSet { public static void main(String[] args) { // Scores are kept sorted (ascending) automatically on every insert TreeSet<Integer> scores = new TreeSet<>(); scores.add(4200); scores.add(1500); scores.add(8750); scores.add(3300); scores.add(9100); scores.add(4200); // duplicate — silently ignored, just like any Set System.out.println("All scores (always sorted): " + scores); // → [1500, 3300, 4200, 8750, 9100] // Lowest and highest score in O(1) System.out.println("Lowest score : " + scores.first()); // 1500 System.out.println("Highest score: " + scores.last()); // 9100 // Who is just below or at the 'bronze' cutoff of 4000? // floor() returns the greatest element <= the given value System.out.println("Highest score at or below 4000: " + scores.floor(4000)); // 3300 // Who barely made it into the top tier (above 4000)? // ceiling() returns the smallest element >= the given value System.out.println("Lowest score at or above 4001: " + scores.ceiling(4001)); // 4200 // Scores strictly below 8000 — headSet is exclusive of the bound by default NavigableSet<Integer> midTier = scores.headSet(8000); System.out.println("Mid-tier scores (below 8000): " + midTier); // [1500, 3300, 4200] // Scores from 3000 to 8999 inclusive — subSet with booleans for inclusivity NavigableSet<Integer> mainBracket = scores.subSet(3000, true, 9000, false); System.out.println("Main bracket [3000, 9000): " + mainBracket); // [3300, 4200, 8750] // Iterate in DESCENDING order — no sorting needed, just a reversed view System.out.print("Top-to-bottom: "); for (int score : scores.descendingSet()) { System.out.print(score + " "); // 9100 8750 4200 3300 1500 } System.out.println(); } }
Lowest score : 1500
Highest score: 9100
Highest score at or below 4000: 3300
Lowest score at or above 4001: 4200
Mid-tier scores (below 8000): [1500, 3300, 4200]
Main bracket [3000, 9000): [3300, 4200, 8750]
Top-to-bottom: 9100 8750 4200 3300 1500
TreeMap — Sorted Keys With All the Power of a Map
TreeMap is to HashMap what TreeSet is to HashSet: it keeps all its keys in sorted order at all times, and it exposes a rich NavigableMap API for range queries, boundary lookups, and sliced views.
The classic use case is any kind of timeline, schedule, or rank-ordered dataset. Imagine you're building a task scheduler. Each task has a deadline (the key) and a description (the value). A TreeMap lets you instantly find the next task due, all tasks due before a certain date, or every task in a given window — without scanning the entire map.
TreeMap also implements SortedMap and NavigableMap, which means you get firstKey(), lastKey(), floorKey(), ceilingKey(), lowerKey(), higherKey(), headMap(), tailMap(), and subMap() — all backed by the same O(log n) Red-Black Tree. You can even get a descending view of the entire map with descendingMap(). These aren't convenience extras; they're the whole reason to choose TreeMap over HashMap.
import java.time.LocalDate; import java.util.Map; import java.util.NavigableMap; import java.util.TreeMap; public class TaskSchedulerTreeMap { public static void main(String[] args) { // Keys (deadlines) are kept sorted chronologically — LocalDate implements Comparable TreeMap<LocalDate, String> schedule = new TreeMap<>(); schedule.put(LocalDate.of(2025, 7, 15), "Submit tax return"); schedule.put(LocalDate.of(2025, 6, 30), "Renew software licences"); schedule.put(LocalDate.of(2025, 8, 1), "Team performance reviews"); schedule.put(LocalDate.of(2025, 7, 4), "Deploy v2.0 to production"); schedule.put(LocalDate.of(2025, 6, 20), "Finish API documentation"); // Iterating a TreeMap always gives keys in ascending (chronological) order System.out.println("--- Full schedule (chronological) ---"); for (Map.Entry<LocalDate, String> task : schedule.entrySet()) { System.out.println(task.getKey() + " -> " + task.getValue()); } LocalDate today = LocalDate.of(2025, 7, 1); // What is the very next task from today? firstKey() of the tailMap from today // ceilingKey returns the smallest key >= today LocalDate nextDeadline = schedule.ceilingKey(today); System.out.println("\nNext task from " + today + ": " + nextDeadline + " — " + schedule.get(nextDeadline)); // What was the most recent task before today? // lowerKey returns the greatest key strictly < today LocalDate previousDeadline = schedule.lowerKey(today); System.out.println("Most recent past task: " + previousDeadline + " — " + schedule.get(previousDeadline)); // Everything overdue (strictly before today) — headMap is exclusive of the bound NavigableMap<LocalDate, String> overdue = schedule.headMap(today, false); System.out.println("\n--- Overdue tasks ---"); overdue.forEach((date, task) -> System.out.println(date + " -> " + task)); // Tasks due in July 2025 — subMap with inclusive/exclusive bounds LocalDate julyStart = LocalDate.of(2025, 7, 1); LocalDate julyEnd = LocalDate.of(2025, 7, 31); NavigableMap<LocalDate, String> julyTasks = schedule.subMap(julyStart, true, julyEnd, true); // both inclusive System.out.println("\n--- July 2025 tasks ---"); julyTasks.forEach((date, task) -> System.out.println(date + " -> " + task)); // Most urgent task overall System.out.println("\nMost urgent task: " + schedule.firstKey() + " — " + schedule.firstEntry().getValue()); } }
2025-06-20 -> Finish API documentation
2025-06-30 -> Renew software licences
2025-07-04 -> Deploy v2.0 to production
2025-07-15 -> Submit tax return
2025-08-01 -> Team performance reviews
Next task from 2025-07-01: 2025-07-04 — Deploy v2.0 to production
Most recent past task: 2025-06-30 — Renew software licences
--- Overdue tasks ---
2025-06-20 -> Finish API documentation
2025-06-30 -> Renew software licences
--- July 2025 tasks ---
2025-07-04 -> Deploy v2.0 to production
2025-07-15 -> Submit tax return
Most urgent task: 2025-06-20 — Finish API documentation
Custom Ordering With Comparator — When Natural Order Isn't Enough
Natural order works great for Strings and numbers, but what about your own objects? And what if you want reverse order, or a case-insensitive sort? That's where a Comparator comes in.
Both TreeMap and TreeSet accept a Comparator in their constructor. Once you supply one, it completely overrides natural order — even if your objects implement Comparable. This is powerful, but there's a critical rule: the Comparator you use for ordering becomes the equality definition for the collection. Two elements are considered duplicates if comparator.compare(a, b) == 0, not if a.equals(b). This surprises many developers.
A practical pattern: pass Comparator.reverseOrder() to get a descending TreeMap, which is perfect for leaderboards where you want the highest value first. Or pass String.CASE_INSENSITIVE_ORDER to a TreeSet of strings so 'Apple' and 'apple' are treated as the same entry. The Comparator is your formatting rule for the entire collection.
import java.util.Comparator; import java.util.TreeMap; import java.util.TreeSet; public class CustomComparatorDemo { // A simple product record — does NOT implement Comparable record Product(String name, double price) {} public static void main(String[] args) { // --- Example 1: Descending Integer TreeMap (leaderboard, highest first) --- // Comparator.reverseOrder() flips the natural ascending order TreeMap<Integer, String> topScorers = new TreeMap<>(Comparator.reverseOrder()); topScorers.put(4200, "Alice"); topScorers.put(9100, "Bob"); topScorers.put(3300, "Carol"); topScorers.put(8750, "Dave"); System.out.println("--- Leaderboard (highest score first) ---"); topScorers.forEach((score, name) -> System.out.println(score + " pts -> " + name)); // --- Example 2: Case-insensitive TreeSet --- // String.CASE_INSENSITIVE_ORDER treats 'Apple' == 'apple' TreeSet<String> caseInsensitiveTags = new TreeSet<>(String.CASE_INSENSITIVE_ORDER); caseInsensitiveTags.add("Java"); caseInsensitiveTags.add("python"); caseInsensitiveTags.add("JAVA"); // treated as duplicate of 'Java' — ignored caseInsensitiveTags.add("Spring"); caseInsensitiveTags.add("Python"); // treated as duplicate of 'python' — ignored System.out.println("\n--- Case-insensitive tag set ---"); System.out.println(caseInsensitiveTags); // Only 3 unique tags // --- Example 3: TreeSet of custom objects sorted by price, then name --- Comparator<Product> byPriceThenName = Comparator .comparingDouble(Product::price) .thenComparing(Product::name); TreeSet<Product> catalogue = new TreeSet<>(byPriceThenName); catalogue.add(new Product("Keyboard", 79.99)); catalogue.add(new Product("Mouse", 49.99)); catalogue.add(new Product("Monitor", 349.99)); catalogue.add(new Product("Webcam", 79.99)); // same price as Keyboard — thenComparing keeps both System.out.println("\n--- Product catalogue (cheapest first) ---"); catalogue.forEach(p -> System.out.printf("%-12s $%.2f%n", p.name(), p.price())); } }
9100 pts -> Bob
8750 pts -> Dave
4200 pts -> Alice
3300 pts -> Carol
--- Case-insensitive tag set ---
[Java, python, Spring]
--- Product catalogue (cheapest first) ---
Mouse $49.99
Keyboard $79.99
Webcam $79.99
Monitor $349.99
TreeMap vs HashMap vs TreeSet vs HashSet — Choosing the Right Tool
The most common mistake is defaulting to HashMap or HashSet out of habit and then discovering you need sorted access later — at which point you're either converting structures or adding sort calls everywhere. Choosing right from the start costs nothing.
The decision is straightforward: if you need to ask range questions ('everything between X and Y'), boundary questions ('what's the closest element to Z?'), or if iteration order must be predictable and sorted, use the Tree variant. If you only ever ask point questions ('does this key exist?', 'give me this value') and don't care about order, stick with the Hash variant for its faster O(1) average operations.
LinkedHashMap and LinkedHashSet are the middle ground — they maintain insertion order but don't sort. Use them when you want predictable iteration without the overhead of sorting. The table below captures the key trade-offs so you can settle this question in seconds during a code review.
import java.util.*; public class ChoosingTheRightCollection { public static void main(String[] args) { List<String> words = List.of("banana", "apple", "cherry", "date", "apple", "fig"); // --- HashSet: Fast uniqueness check, unpredictable iteration order --- Set<String> hashSet = new HashSet<>(words); System.out.println("HashSet (unordered, no dupes): " + hashSet); // Output order is unpredictable // --- LinkedHashSet: Unique + preserves insertion order --- Set<String> linkedSet = new LinkedHashSet<>(words); System.out.println("LinkedHashSet (insertion order): " + linkedSet); // banana, apple, cherry, date, fig // --- TreeSet: Unique + always alphabetically sorted --- Set<String> treeSet = new TreeSet<>(words); System.out.println("TreeSet (always sorted) : " + treeSet); // apple, banana, cherry, date, fig System.out.println(); // Simulate word frequency counter String sentence = "the quick brown fox jumps over the lazy dog the fox"; String[] tokens = sentence.split(" "); // HashMap: O(1) lookup, random order Map<String, Integer> hashFreq = new HashMap<>(); for (String word : tokens) { hashFreq.merge(word, 1, Integer::sum); } System.out.println("HashMap frequency (random order):\n" + hashFreq); // TreeMap: O(log n) lookup, but keys are alphabetically ordered Map<String, Integer> treeFreq = new TreeMap<>(hashFreq); // copy into sorted map System.out.println("\nTreeMap frequency (alphabetical):\n" + treeFreq); // Range query: words starting with letters 'f' through 'q' NavigableMap<String, Integer> fToQ = ((TreeMap<String, Integer>) treeFreq).subMap("f", true, "r", false); System.out.println("\nWords f–q: " + fToQ); } }
LinkedHashSet (insertion order): [banana, apple, cherry, date, fig]
TreeSet (always sorted) : [apple, banana, cherry, date, fig]
HashMap frequency (random order):
{the=3, quick=1, brown=1, fox=2, jumps=1, over=1, lazy=1, dog=1}
TreeMap frequency (alphabetical):
{brown=1, dog=1, fox=2, jumps=1, lazy=1, over=1, quick=1, the=3}
Words f–q: {fox=2, jumps=1, lazy=1, over=1}
| Feature / Aspect | TreeMap / TreeSet | HashMap / HashSet |
|---|---|---|
| Internal structure | Red-Black Tree | Hash Table (array of buckets) |
| Iteration order | Always sorted (natural or Comparator) | Unpredictable (effectively random) |
| get / contains | O(log n) worst case | O(1) average, O(n) worst case |
| put / add | O(log n) worst case | O(1) average, O(n) worst case |
| Range queries (subMap, headSet…) | Built-in, O(log n) | Not supported — requires full scan |
| Null keys allowed | No — throws NullPointerException | Yes (one null key for HashMap) |
| Null values allowed (Map only) | Yes | Yes |
| Thread safety | Not thread-safe | Not thread-safe |
| Memory overhead | Higher (tree node pointers) | Lower (flat array) |
| Best used when | Sorted iteration or range queries needed | Maximum speed, order doesn't matter |
🎯 Key Takeaways
- TreeMap and TreeSet use a Red-Black Tree internally, guaranteeing O(log n) for every insert, delete, and lookup — but also for range queries that HashMap/HashSet can't even do efficiently.
- The Comparator you pass to a TreeMap or TreeSet is the equality definition — compare() returning 0 means 'same element', regardless of what equals() says. Always add a tiebreaker or you'll silently lose data.
- The NavigableMap and NavigableSet APIs (floor, ceiling, headMap, tailSet, subMap) are the real reason to choose TreeMap/TreeSet. If you're not using at least one of those methods, you probably want a HashMap/HashSet instead.
- Never mutate an object's fields that affect its sort order after inserting it as a key or element — the tree won't re-sort itself and the collection's integrity breaks silently with no exception thrown.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Storing objects in TreeSet without Comparable or a Comparator — When you add a custom class like
Employeeto a TreeSet without implementing Comparable or supplying a Comparator, you'll get a ClassCastException at runtime (not compile time) on the second insertion: 'Employee cannot be cast to Comparable'. Fix: implement Comparablein your class, or pass a Comparator to the TreeSet constructor. The error appears at the second add() because that's when TreeSet first tries to compare two elements. - ✕Mistake 2: Assuming comparator.compare(a, b) == 0 means the element is rejected as a duplicate when you didn't intend it — A developer creates a TreeSet
with a Comparator that sorts only by price. Two products with the same price but different names are treated as the same element; the second one is silently discarded. The set ends up with fewer entries than expected and no exception is thrown. Fix: always include a tiebreaker in your Comparator (e.g., .thenComparing(Product::name)) so that compare() returns 0 only when the objects are genuinely the same. - ✕Mistake 3: Mutating a key's fields after inserting it into a TreeMap or TreeSet — TreeMap and TreeSet don't re-sort entries when an existing object's state changes. If you insert a Product keyed by price, then change that product's price field externally, the tree structure becomes corrupted — lookups may fail or return wrong results, and the collection's sorted invariant is silently broken. Fix: treat keys as immutable after insertion, or use immutable value types (records, Strings, primitives). If you must change a key, remove it, mutate it, then re-insert.
Interview Questions on This Topic
- QWhat is the internal data structure behind TreeMap in Java, and why was that structure chosen over a plain binary search tree?
- QIf a TreeMap and a HashMap both store the same 10 million entries, under what specific conditions would you choose the TreeMap despite its slower O(log n) operations?
- QA colleague stores mutable objects as keys in a TreeMap and later complains that containsKey() returns false for an object that is clearly in the map. What is happening, and how would you fix it without changing the caller's code?
Frequently Asked Questions
Does TreeMap allow null keys in Java?
No. TreeMap throws a NullPointerException if you try to insert a null key, because it must call compareTo() or the Comparator on every key during insertion, and invoking a method on null causes the exception. Null values (not keys) are perfectly fine. If you need null key support with sorted iteration, you'd have to handle the null case manually in a custom Comparator — but it's usually cleaner to use a sentinel value instead.
Is TreeMap thread-safe?
No, TreeMap is not thread-safe. Concurrent reads and writes from multiple threads can corrupt the internal Red-Black Tree structure. Wrap it with Collections.synchronizedSortedMap(new TreeMap<>()) for basic synchronisation, or use ConcurrentSkipListMap from java.util.concurrent, which provides thread-safe sorted map operations with better concurrent throughput than a synchronised TreeMap.
What's the difference between floorKey and lowerKey in TreeMap?
floorKey(k) returns the greatest key that is less than or equal to k — so it includes k itself if it exists. lowerKey(k) returns the greatest key strictly less than k — it never returns k even if k is present. The same distinction applies to ceilingKey (>=) vs higherKey (>). Think of floor/ceiling as inclusive bounds and lower/higher as exclusive bounds.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.