TreeMap in Java – SortedMap and Red-Black Tree Explained for High-Performance Sorted Collections

Need a Map that keeps your keys in sorted order—automatically? TreeMap does exactly that. Unlike HashMap, which gives you fast access but no ordering guarantees, TreeMap ensures that entries are always sorted by their keys, thanks to an underlying Red-Black Tree.

In this in-depth tutorial, we’ll explore how TreeMap works, when to use it, how it compares to other maps, and how to make the most of its ordering capabilities in modern Java development.

---

Table of Contents

• What is TreeMap?
• Java Syntax and Constructors
• SortedMap and NavigableMap Interface
• Internal Working: Red-Black Tree
• Performance and Big-O Complexity
• Real-World Use Cases
• Functional Programming Support (Java 8+)
• Java Version Enhancements (Java 8–21)
• Comparisons with Other Maps
• Pros and Cons
• Anti-patterns and Common Pitfalls
• Refactoring Code with TreeMap
• Best Practices
• 📌 What's New in Java [version]?
• Conclusion and Key Takeaways
• FAQ – 10 Expert-Level Questions

What is TreeMap?

TreeMap is an implementation of the SortedMap and NavigableMap interfaces in Java. It stores key-value pairs in a sorted order defined by natural ordering or a custom Comparator.

TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("Alice", 90);
scores.put("Bob", 85);
scores.put("Charlie", 95);
System.out.println(scores); // Sorted by keys alphabetically

Java Syntax and Constructors

TreeMap<K, V> treeMap = new TreeMap<>();
TreeMap<K, V> treeMap = new TreeMap<>(Comparator.reverseOrder());

SortedMap and NavigableMap Interface

TreeMap implements:

• SortedMap: Provides firstKey(), lastKey(), subMap(), etc.
• NavigableMap: Adds navigation methods like ceilingKey(), floorKey(), pollFirstEntry().

Internal Working: Red-Black Tree

Internally, TreeMap uses a self-balancing Red-Black Tree.

Red-Black Tree Properties:

1. Each node is either red or black
2. Root is always black
3. Red nodes cannot have red children
4. Every path from root to null has same number of black nodes
5. Ensures O(log n) time complexity for search, insert, delete

Unlike HashMap, no hashing is involved. All operations are based on comparison.

Performance and Big-O Complexity

Operation	Time Complexity
get/put/remove	O(log n)
iteration	O(n)
range queries	O(log n)

Real-World Use Cases

• Maintaining a leaderboard (sorted by score)
• Implementing range filters
• Prefix-based search (using subMap)
• Financial applications where sorted keys matter

Functional Programming Support

TreeMap<String, Integer> map = new TreeMap<>();
map.put("A", 100);
map.put("B", 50);
map.put("C", 200);

map.entrySet().stream()
   .filter(e -> e.getValue() > 100)
   .forEach(e -> System.out.println(e.getKey()));

Java Version Enhancements

Java 8

• Lambda-friendly operations
• forEach, computeIfAbsent, merge, etc.

Java 9

• Immutable maps via Map.of(), though TreeMap itself is mutable

Java 10

• var for local variable declarations

Java 21

• Minor improvements in Comparator chaining and Red-Black Tree tuning

Comparisons with Other Maps

Feature	HashMap	LinkedHashMap	TreeMap
Order	None	Insertion/Access	Sorted by key
Performance	O(1) avg	O(1)	O(log n)
Null keys	Allowed (1)	Allowed (1)	Not allowed
Thread-safe	No	No	No

Pros and Cons

✅ Pros

• Keys are always sorted
• Fast range queries
• Full support for NavigableMap

❌ Cons

• Slower than HashMap (O(log n))
• No null keys allowed

Anti-patterns and Common Pitfalls

❌ Using null as key

TreeMap<String, String> map = new TreeMap<>();
map.put(null, "value"); // Throws NullPointerException

❌ Using TreeMap when order is not needed

Stick to HashMap if sorting isn't required.

Refactoring Code with TreeMap

Before (manual sorting):

Map<String, Integer> unsorted = new HashMap<>();
// Manually sort entries

After:

Map<String, Integer> sorted = new TreeMap<>(unsorted);

Best Practices

• Always provide a Comparator for custom key ordering
• Avoid using expensive compareTo() in key classes
• Prefer subMap() or tailMap() for range views

📌 What's New in Java [version]?

Java 8

• forEach(), merge(), compute()
• Stream-friendly entrySets

Java 9

• Map.of() methods for quick immutables

Java 10

• Local variable inference with var

Java 21

• Internal tuning for balanced tree traversal and memory optimization

Conclusion and Key Takeaways

• TreeMap is ideal when key order matters.
• It uses Red-Black Tree to guarantee O(log n) performance.
• Avoid TreeMap when high-frequency access or null keys are needed.
• Java 8+ features make working with TreeMap expressive and functional.

FAQ – 10 Expert-Level Questions

1. Can TreeMap have null keys?

No. A NullPointerException is thrown.

2. What is the default sort order in TreeMap?

Natural ordering using Comparable interface.

3. How does TreeMap differ from HashMap?

TreeMap is sorted and slower; HashMap is unordered but faster.

4. Is TreeMap thread-safe?

No. Use Collections.synchronizedSortedMap() or ConcurrentSkipListMap.

5. What is the underlying data structure?

Red-Black Tree.

6. Can I iterate TreeMap in reverse order?

Yes, use descendingMap() or descendingKeySet().

7. What happens if keys are not comparable?

Throws ClassCastException unless a Comparator is provided.

8. Is TreeMap faster than TreeSet?

They're internally similar; TreeSet is a wrapper over TreeMap.

9. Can TreeMap be made immutable?

Yes, via Collections.unmodifiableMap() or Java 9's Map.of().

10. When to use TreeMap over LinkedHashMap?

When key sorting is required, not just ordering by insertion.

---