TreeMap and TreeSet in Java

TreeMap and TreeSet provide sorted, ordered collections backed by a Red-Black tree data structure. Unlike HashMap and HashSet which offer O(1) average operations but no ordering guarantees, TreeMap and TreeSet maintain elements in sorted order and provide O(log n) worst-case performance for all operations.

Introduction

TreeMap and TreeSet are the sorted counterparts to HashMap and HashSet in Java’s collection framework. Where HashMap provides O(1) average-case operations with no ordering guarantees, TreeMap maintains keys in sorted order and guarantees O(log n) worst-case performance for every operation. This guarantee matters when you need deterministic performance, range queries, or ordered iteration — scenarios where HashMap’s O(n) worst-case is unacceptable.

The underlying data structure is a Red-Black tree — a self-balancing binary search tree that maintains O(log n) height through color flips and rotations during insertions and deletions. This means no pathological degradation even with adversarial insertion sequences, unlike a naive BST that could become a linked list with sorted input. TreeSet is implemented identically to TreeMap, using a dummy value internally, so everything here applies equally to both.

This post covers when to choose TreeMap over HashMap (and TreeSet over HashSet), how the Red-Black tree maintains balance, the O(log n) complexity guarantees for all operations, the null key restriction and why it exists, range operations like subMap, headMap, and tailMap, and the nearest-key methods (lowerKey, floorKey, ceilingKey, higherKey) that make TreeMap powerful for navigation problems.

When to Use TreeMap

Use TreeMap when:

• You need key-value pairs sorted by key
• You need range operations (subMap, headMap, tailMap)
• You need O(log n) guaranteed performance
• You need to find the closest key below or above a given key

Do not use TreeMap when:

• O(1) performance is critical and ordering is not needed
• You have extremely high write throughput (TreeMap is slower than HashMap)
• You need to store null keys (TreeMap does not allow null keys)

TreeSet Use Cases

Use TreeSet when:

• You need sorted unique elements
• You need to find the smallest or largest element
• You need range queries on a sorted set

Do not use TreeSet when:

• You need O(1) containment checks and do not need ordering
• You need insertion-order preservation

Red-Black Tree Fundamentals

TreeMap uses a Red-Black tree — a self-balancing binary search tree that guarantees O(log n) height by recoloring and rotating nodes during insertions and deletions. The tree maintains these invariants:

1. Every node is either red or black
2. The root is black
3. All leaves (NIL nodes) are black
4. Red nodes cannot have red children
5. Every path from a node to its leaves has the same number of black nodes

Red-Black Tree Structure

graph TD
    A["8 (Black)"] --> B["3 (Red)"]
    A --> H["10 (Black)"]
    B --> C["1 (Black)"]
    B --> D["6 (Red)"]
    C --> E["NIL"]
    C --> F["NIL"]
    D --> G["NIL"]
    D --> I["NIL"]
    H --> J["NIL"]
    H --> K["NIL"]

TreeMap vs HashMap Comparison

graph LR
    A["TreeMap<K,V><br/>Sorted<br/>O(log n) operations<br/>Red-Black tree"] --> B["Use when:<br/>- Ordering required<br/>- Range queries<br/>- Guaranteed performance"]
    C["HashMap<K,V><br/>Unsorted<br/>O(1) avg operations<br/>Hash table"] --> D["Use when:<br/>- Fast lookups<br/>- No ordering needed<br/>- High throughput"]

Failure Scenarios

Scenario	Cause	Result
NullPointerException	Inserting null key (TreeMap requires natural ordering or comparator)	Runtime crash
ClassCastException	Keys that cannot be compared	Runtime crash
NoSuchElementException	Calling firstKey() / lastKey() on empty map	Runtime crash
IllegalArgumentException	Inconsistent ordering between modifications	Runtime crash

Trade-Off Table

Aspect	TreeMap	HashMap
Ordering	Sorted by key	None
Get/Put complexity	O(log n) guaranteed	O(1) average, O(n) worst
Range operations	Yes (subMap, headMap)	No
null key	Not allowed	One allowed
Memory overhead	Lower (no pointer per entry)	Higher (bucket array)
Iteration order	Sorted	Undefined

Code Snippets

Basic TreeMap Operations

Map<String, Integer> scores = new TreeMap<>();
scores.put("Alice", 95);
scores.put("Bob", 82);
scores.put("Charlie", 91);
System.out.println(scores.firstKey());   // "Alice"
System.out.println(scores.lastKey());     // "Charlie"
System.out.println(scores.lowerEntry("Bob"));  // Alice's entry
System.out.println(scores.subMap("Alice", "Charlie"));  // Alice + Bob

TreeSet Operations

TreeSet<Integer> nums = new TreeSet<>();
nums.addAll(List.of(5, 2, 8, 1, 9));
System.out.println(nums.first());  // 1
System.out.println(nums.last());  // 9
System.out.println(nums.lower(5)); // 2
System.out.println(nums.higher(5)); // 8
System.out.println(nums.subSet(2, 8)); // [2, 5] — inclusive lower, exclusive upper

Custom Comparable Key

class Person implements Comparable<Person> {
    private final String name;
    private final int age;

    @Override
    public int compareTo(Person o) {
        int cmp = this.name.compareTo(o.name);
        return cmp != 0 ? cmp : Integer.compare(this.age, o.age);
    }
}

Observability Checklist

• Monitor tree depth — depth should remain O(log n) despite many insertions
• Track ClassCastException in production to detect type mismatches in TreeMap keys
• Profile compare operations in hot paths — compare is O(log n) per operation
• Log subMap() calls to detect range query patterns that may indicate full-scan alternatives
• Monitor NullPointerException from null key attempts

Security Notes

• TreeMap and TreeSet are not thread-safe
• Sorted order means that iterating over the collection reveals the sorted arrangement of data — consider this when the sorted order itself is sensitive
• The comparator or Comparable.compareTo() should not leak sensitive state
• Collections.unmodifiableMap() and Set.of() create immutable views for security-sensitive use cases

Common Pitfalls / Anti-Patterns

1. null key: TreeMap does not allow null keys because it uses compareTo() which would throw NullPointerException if the key is null. Use HashMap if you need null key support.
2. Inconsistent comparators: If you use a TreeMap(Comparator) and then modify the comparator’s behavior, the map becomes corrupted
3. Confusing subMap() bounds: subMap(from, to) is half-open — inclusive of from, exclusive of to
4. TreeSet vs TreeMap: TreeSet is to TreeMap as HashSet is to HashMap — TreeSet internally uses a TreeMap with dummy values, just like HashSet uses HashMap
5. Comparator vs Comparable: If elements implement Comparable, you can use the no-arg constructor; otherwise, pass a Comparator to the constructor

Quick Recap

• TreeMap is a sorted key-value map backed by a Red-Black tree; TreeSet wraps a TreeMap internally
• All operations are O(log n) guaranteed — no worst-case degradation
• Elements must be mutually comparable — either implement Comparable or provide a Comparator
• null keys are not allowed in TreeMap
• Range operations (subMap, headMap, tailMap) are available and O(log n)

Interview Questions

Further Reading

• Oracle TreeMap Documentation — Official API specification
• Baeldung: TreeMap Internals — Red-Black tree mechanics and sorted map operations
• Red-Black Tree Visualization — Interactive visualization of Red-Black tree insertion and deletion operations
• TreeSet vs HashSet vs LinkedHashSet — Comprehensive comparison of Set implementations

Conclusion

TreeMap and TreeSet are the ordered counterparts to HashMap and HashSet. Where HashMap prioritizes speed with O(1) average operations, TreeMap guarantees O(log n) worst-case performance and maintains keys in sorted order. That tradeoff matters when you need range queries, sorted iteration, or guaranteed performance without hash collision risk.

The null key restriction is the most common stumbling block — TreeMap requires a total ordering, which null cannot satisfy. For nearest-key operations like lowerKey() and ceilingKey(), TreeMap excels at O(log n) performance. TreeSet is simply TreeMap with dummy values, so everything here applies equally.

TreeMap and TreeSet are the natural next step after HashMap and HashSet when ordering becomes a requirement. If you also need queue or deque behavior, Queue and Deque covers heap-based priority ordering.