TreeMap

Imagine you are building a massive warehouse. If your only goal is to throw incoming items into storage and retrieve them instantly using a unique barcode, a hash table like Java's HashMap can be very useful. It tosses items into random buckets using mathematical hash codes, allowing you to fetch any specific item in a fraction of a millisecond. But what happens if you walk into that warehouse and ask: "Give me all items priced between $10 and$20," or "Show me the next most expensive item after this one"? When using a hash table, your only option is to open and inspect every single box in the entire building, which can be a very inefficient process.

In the Java Collections Framework, maps associate unique keys with values. While HashMap is the most common implementation, providing an average-case constant-time complexity of $O(1)$ for basic operations, it does not guarantee any iteration order. If your application requires entries to be sorted at all times, Java provides the TreeMap class.

Java TreeMap

A TreeMap is a sorted, tree-based implementation of the Map interface. Unlike hash tables, it does not use hashing. Instead, it maintains its keys in a strict, sorted order. This sorting can follow the natural ordering of the keys or a custom ordering defined by a Comparator provided at map construction. This structural guarantee comes with a minor performance trade-off: operations such as insertion, retrieval, and deletion run with a logarithmic time complexity of $O(log n)$.

To understand the capabilities of TreeMap, we can analyze its position within the Java hierarchy:

TreeMap implements the NavigableMap interface, which in turn extends the SortedMap interface. SortedMap itself extends the SequencedMap interface, which finally extends the Map interface. TreeMap also extends the abstract class AbstractMap, which again implements Map.

• Map: Defines the fundamental concept of key-value pairs.

• SortedMap: Extends Map to guarantee that keys are maintained in a total ordering. It introduces range-view methods (subMap(), headMap(), tailMap()) and endpoint queries — but note that at this level, those endpoint queries are limited to firstKey() and lastKey(), which return only the key.

• NavigableMap: Extends SortedMap to add navigation methods. These methods help us find the closest matching keys relative to a search target: floorKey(), ceilingKey(), lowerKey(), and higherKey(), along with their entry-returning counterparts floorEntry(), ceilingEntry(), lowerEntry(), and higherEntry(). NavigableMap also introduces firstEntry() and lastEntry(), which return the full Map.Entry rather than just the key. Together, these methods transform the map from a simple sorted container into a searchable index.

It's worth noting that SequencedMap is a relatively recent addition to this hierarchy — it was introduced in Java 21 to give collections with a defined encounter order (like TreeMap and LinkedHashMap) a common set of methods for working with that order.

Internal working mechanism

In a binary search tree (BST), every node follows a simple ordering rule: the left child is always smaller than its parent, and the right child is always greater. This property makes ordered traversal and fast lookups possible in the first place. A standard BST provides an average-case search complexity of $O(log n)$. However, if you insert elements in sorted order (for example, 1, 2, 3, 4, 5), a standard BST degenerates into a linear structure resembling a linked list. In this worst-case scenario, performance degrades to $O(n)$.

To guarantee logarithmic performance regardless of insertion order, TreeMap uses a Red-Black Tree as its backing structure. A Red-Black Tree is a self-balancing binary search tree that provides a good balance between search performance and the cost of maintaining balance. Each node in the tree stores a key-value pair and contains an internal color bit, designated as either red or black. The structure enforces five invariant rules to maintain balance:

1. Each node is colored either red or black.

2. The root node of the tree is always black.

3. All terminal NIL leaves (empty leaf placeholders) are considered black.

4. No Red-Red conflicts: A red node cannot have red children (no two red nodes can be adjacent along any path).

5. Black-height consistency: Every path from a node to any of its descendant NIL leaves must contain the exact same number of black nodes.

These properties guarantee that the longest path from the root to any leaf is at most twice as long as the shortest path.

Internally, the structure represents each node with a private static Entry class that holds the key, the value, references to its left child, right child, and parent, and the color bit:

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
}

The image below shows visually what a red-black tree looks like — the black root at the top, with red nodes never sitting adjacent to one another, and every path down to a leaf passing through the same number of black nodes.

Structural rebalancing

Two of the most important methods in creating a TreeMap are the put() and remove() methods. When you modify a TreeMap via put() or remove(), the tree may violate these properties. The tree automatically executes two recovery mechanisms:

• Recoloring: Flipping the color bit of nodes to restore color balance rules.

• Rotations: Shifting parent-child pointer relationships to physically restructure and rebalance the tree. A Left Rotation elevates a node's right child, while a Right Rotation elevates a node's left child.

During insertion, the tree requires at most two rotations to restore balance. During deletion, it requires at most three. This maintains a guaranteed performance limit of $O(log n)$ for search, insertion, and deletion.

Natural vs. custom ordering

Since TreeMap relies on comparisons to place nodes, all keys must either implement Comparable or be comparable through the provided Comparator. You can establish this ordering in two ways:

1. If you construct a TreeMap using the default constructor, the keys are sorted according to their natural ordering. For this to work, the key class must implement the Comparable interface, and keys must be mutually comparable (for instance, you cannot compare a String to an Integer). Otherwise, a ClassCastException will be thrown:

   import java.util.TreeMap;
   
   public class NaturalOrderingDemo {
       public static void main(String[] args) {
           TreeMap<String, Integer> studentGrades = new TreeMap<>();
           studentGrades.put("Charlie", 88);
           studentGrades.put("Alice", 95);
           studentGrades.put("Bob", 91);
   
           // Iteration follows alphabetical (natural) order
           System.out.println(studentGrades);
           // Output: {Alice=95, Bob=91, Charlie=88}
       }
   }
   

2. If you want to sort elements in a non-standard order, you can pass a custom Comparator to the TreeMap constructor:

   import java.util.Comparator;
   import java.util.TreeMap;
   
   public class CustomOrderingDemo {
       public static void main(String[] args) {
           // Sort strings in reverse alphabetical order
           TreeMap<String, Integer> reverseGrades = new TreeMap<>(Comparator.reverseOrder());
           reverseGrades.put("Charlie", 88);
           reverseGrades.put("Alice", 95);
           reverseGrades.put("Bob", 91);
   
           System.out.println(reverseGrades);
           // Output: {Charlie=88, Bob=91, Alice=95}
       }
   }
   

Navigational methods and range queries

The implementation of NavigableMap provides highly functional methods for relative key lookups and range operations. TreeMap allows you to locate adjacent keys or entries even if the exact target key is not present in the map:

• floorKey(K key): Returns the greatest key less than or equal to the target.

• ceilingKey(K key): Returns the smallest key greater than or equal to the target.

• lowerKey(K key): Returns the greatest key strictly less than the target.

• higherKey(K key): Returns the smallest key strictly greater than the target.

• floorEntry(K key): Returns the entry (key and value) with the greatest key less than or equal to the target.

• ceilingEntry(K key): Returns the entry with the smallest key greater than or equal to the target.

• lowerEntry(K key): Returns the entry with the greatest key strictly less than the target.

• higherEntry(K key): Returns the entry with the smallest key strictly greater than the target.

If you are managing scheduled times, you can determine if a requested slot conflicts with existing entries or identify the nearest open slots:

import java.util.TreeMap;

public class Scheduler {
    public static void main(String[] args) {
        TreeMap<Integer, String> appointments = new TreeMap<>();
        appointments.put(900, "Breakfast Meeting");
        appointments.put(1030, "Code Review");
        appointments.put(1300, "Client Call");

        int requestedTime = 1100;

        // Find closest bookings around 11:00 AM
        Integer previousBooking = appointments.floorKey(requestedTime); // 1030
        Integer nextBooking = appointments.ceilingKey(requestedTime);   // 1300

        System.out.println("Slot before 11:00: " + previousBooking);
        System.out.println("Slot after 11:00: " + nextBooking);
    }
}

Besides this, you can extract specific regions of a map using view methods:

• subMap(fromKey, toKey): Entries between fromKey (inclusive) and toKey (exclusive).

• headMap(toKey): Entries with keys strictly less than toKey.

• tailMap(fromKey): Entries with keys greater than or equal to fromKey.

import java.util.SortedMap;
import java.util.TreeMap;

public class ViewMethodsDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> appointments = new TreeMap<>();
        appointments.put(900, "Breakfast Meeting");
        appointments.put(1030, "Code Review");
        appointments.put(1300, "Client Call");
        appointments.put(1500, "Team Sync");

        // Entries between 09:00 (inclusive) and 13:00 (exclusive)
        SortedMap<Integer, String> morningSlots = appointments.subMap(900, 1300);
        System.out.println("Morning slots: " + morningSlots);
        // Output: Morning slots: {900=Breakfast Meeting, 1030=Code Review}

        // Entries strictly before 13:00
        SortedMap<Integer, String> beforeLunch = appointments.headMap(1300);
        System.out.println("Before lunch: " + beforeLunch);
        // Output: Before lunch: {900=Breakfast Meeting, 1030=Code Review}

        // Entries from 13:00 onward
        SortedMap<Integer, String> fromLunch = appointments.tailMap(1300);
        System.out.println("From lunch onward: " + fromLunch);
        // Output: From lunch onward: {1300=Client Call, 1500=Team Sync}
    }
}

These methods return backed views, not copies (they do not allocate a new map). The original TreeMap immediately reflects any structural changes in the submap view, and modifications made within the submap view propagate back to the original TreeMap.

Keep in mind that if you attempt to insert a key into a submap view that lies outside the range boundaries defined during the submap's creation, the map will throw an IllegalArgumentException.

Key constraints and pitfalls

When using a TreeMap, there are several critical behavioral rules and structural constraints to keep in mind.

1. Null keys are prohibited: Unlike HashMap, which allows a single null key, TreeMap forbids null keys. Attempting to insert null throws a NullPointerException because the internal comparison methods (compareTo() or compare()) cannot evaluate a null reference against existing keys.

2. Comparison overrides equality: A standard HashMap determines key identity using the equals() and hashCode() methods. TreeMap completely ignores equals() for lookup and insertion. It considers two keys identical if and only if their comparison evaluates to 0.

   If your key's compareTo() method is inconsistent with its equals() method, the class will violate the standard contract of the Map interface.

   import java.math.BigDecimal;
   import java.util.HashMap;
   import java.util.TreeMap;
   
   public class EqualityMismatchDemo {
       public static void main(String[] args) {
           BigDecimal val1 = new BigDecimal("1.0");
           BigDecimal val2 = new BigDecimal("1.00");
   
           // BigDecimal equals() checks precision, so they are not equal
           System.out.println("equals() result: " + val1.equals(val2)); // false
   
           // BigDecimal compareTo() evaluates numerical value, so they match
           System.out.println("compareTo() result: " + val1.compareTo(val2)); // 0
   
           HashMap<BigDecimal, String> hash = new HashMap<>();
           hash.put(val1, "One");
           hash.put(val2, "Two");
           System.out.println("HashMap size: " + hash.size()); // Size: 2
   
           TreeMap<BigDecimal, String> tree = new TreeMap<>();
           tree.put(val1, "One");
           tree.put(val2, "Two");
           System.out.println("TreeMap size: " + tree.size()); // Size: 1 (val2 overwrote val1)
       }
   }
   

3. Iteration efficiency: Many developers iterate over a map by looping through the keys and retrieving the values:

   // Performance warning: O(n log n) operation
   for (String key : sortedMap.keySet()) {
       Integer value = sortedMap.get(key); 
   }
   

   In a HashMap, this is acceptable because .get(key) runs in $O(1)$ time. In a TreeMap, however, .get(key) requires traversing the tree, costing $O(log n)$ operations per lookup. This raises the overall iteration complexity to $O(nlog n)$.

   To iterate efficiently in $O(n)$ time, use entrySet() to retrieve keys and values simultaneously without repeated lookups:

   // Efficient iteration: O(n) operation
   for (Map.Entry<String, Integer> entry : sortedMap.entrySet()) {
       String key = entry.getKey();
       Integer value = entry.getValue();
   }
   

Conclusion

Java's TreeMap is an incredibly useful tool. By hiding the complex logic of a Red-Black tree behind a clean interface, it gives you a simple way to keep your data sorted and searchable. If you know how to use its navigation methods, avoid basic comparison pitfalls, and write efficient loops, you have a solid handle on how to manage data structures in Java.

Choose HashMap when you need the fastest key-based lookups without caring about order. Choose TreeMap when you need keys to remain sorted, perform range queries, or frequently search for neighboring keys.