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

The diagram shows a Red-Black tree storing keys {1, 3, 6, 8, 10}. Each node carries a color — red or black — and NIL placeholders mark the leaf terminators. The root is always black, and every NIL is black too. This coloring scheme is not decorative — it enforces the height bound that gives TreeMap its O(log n) guarantee.

Five invariants define every Red-Black tree: every node is red or black, the root is black, all NIL leaves are black, red nodes never have red children, and every root-to-leaf path has the same count of black nodes. These invariants limit the tree’s height to at most 2 * log2(n + 1) regardless of insertion order. A naive BST degrades into a linked list with sorted input; Red-Black trees prevent this through local rotations and recoloring that restore balance in O(log n) time.

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

TreeMap and HashMap sit at opposite ends of a tradeoff: sorted-but-slower versus unordered-but-faster. The diagram captures this visually, and the table that follows breaks it down dimension by dimension. The choice comes down to whether you need ordering or raw speed.

HashMap distributes entries across a bucket array using hash codes, giving O(1) average lookups and inserts but no inherent ordering — iteration follows hash-seed order, which is effectively random. TreeMap maintains a sorted binary search tree, so iteration always traverses keys in ascending order and range operations like subMap become natural window queries rather than full scans. Every operation costs O(log n) instead of O(1), but for most practical dataset sizes the difference is negligible. The gap widens when key distributions are adversarial: HashMap’s O(n) worst-case can end up slower than TreeMap’s guaranteed O(log n).

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

Trade-Off Table

Code Snippets

Basic TreeMap Operations

TreeMap’s API is built around sorted key navigation. The example below creates a TreeMap storing student names as keys and scores as values, then demonstrates the four primary navigation methods alongside a range query. Each method runs in O(log n) time by walking the Red-Black tree from root to the appropriate node, not by scanning the entire map.

firstKey() and lastKey() return the smallest and largest keys, while lowerEntry() and subMap() enable window queries. The subMap(from, to) call uses a half-open interval, meaning the lower bound is inclusive and the upper bound is exclusive. TreeMap throws NoSuchElementException if you call firstKey() or lastKey() on an empty map, so guard those calls if your map might be empty in production.

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 mirrors TreeMap’s navigation API but operates on a sorted set of elements rather than key-value pairs. The example below builds a TreeSet from a list of integers, then demonstrates boundary lookup and range extraction. Since TreeSet uses the same Red-Black tree backing as TreeMap, all these operations carry the same O(log n) guarantee.

The boundary methods (lower, higher) return null when no element satisfies the condition, unlike first() and last() which throw NoSuchElementException on an empty set. The subSet(from, to) range is half-open, inclusive of the lower bound and exclusive of the upper bound. One common mistake is assuming the upper bound is inclusive. It is not. TreeSet also supports pollFirst() and pollLast() for atomic remove-and-fetch operations, which are useful when implementing priority queues or eviction policies.

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

When the natural ordering of your keys does not match what compareTo() provides, or when you need to use a class you cannot modify, pass a Comparator to the TreeMap constructor. For classes you do control, implementing Comparable is simpler. The example below shows a Person class sorted first by name, then by age within the same name.

The compareTo() implementation follows a standard compound comparison pattern: compare the first field, and only if it is equal (returns 0) proceed to compare the second field. This chain can continue for as many fields as needed. The Integer.compare() method is preferred over subtracting ages because subtraction can overflow with extreme int values. The method must be consistent with equals(). If two objects are equals(), compareTo() must return 0. Otherwise the map will behave unexpectedly when checking containment.

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
• HashMap — unsorted hash-based alternative
• HashSet — unsorted set implementation
• Queue and Deque — ordered collection interfaces

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.