TreeMap in Java – Complete Guide with Examples

TreeMap is a Map that keeps its keys sorted at all times. Whatever order you insert entries in, iterating a TreeMap returns them in ascending key order, or in any order defined by a Comparator. It also finds the nearest key below or above any value and returns key ranges in O(log n) time.

TreeMap lives in java.util, has been part of the Collections Framework since JDK 1.2, and is implemented as a red-black tree. This tutorial covers sorting, custom comparators, navigation methods and practical lookups such as grade bands.

1. What Is a TreeMap?

Think of a phone book: names are always in alphabetical order, each name has one entry, and you can open it at "the first name after K". A TreeMap gives your program the same abilities.

• Keys sorted by natural order (Comparable) or a Comparator.
• O(log n) put, get, remove and containsKey.
• Navigation: floorKey(), ceilingEntry(), headMap(), subMap(), descendingMap() and more.
• No null key with natural ordering; null values are allowed.
• Not synchronized; iterators are fail-fast.

2. Class Hierarchy and Declaration

public class TreeMap<K, V> extends AbstractMap<K, V>
        implements NavigableMap<K, V>, Cloneable, java.io.Serializable

NavigableMap extends SortedMap, which extends Map (and SequencedMap since Java 21).

3. Your First TreeMap Program

import java.util.TreeMap;

public class TreeMapQuickStart {
    public static void main(String[] args) {
        TreeMap<String, Integer> population = new TreeMap<>();
        population.put("Mumbai", 21);
        population.put("Delhi", 33);
        population.put("Chennai", 12);
        population.put("Bengaluru", 14);

        System.out.println("Sorted by city: " + population);
        System.out.println("firstKey():     " + population.firstKey());
        System.out.println("lastEntry():    " + population.lastEntry());
        System.out.println("get(Delhi):     " + population.get("Delhi") + " million");
    }
}

Sorted by city: {Bengaluru=14, Chennai=12, Delhi=33, Mumbai=21}
firstKey():     Bengaluru
lastEntry():    Mumbai=21
get(Delhi):     33 million

4. Constructors

5. Custom Order with a Comparator

A comparator can reverse the order or change what counts as "the same key". A case-insensitive TreeMap is a handy way to store HTTP headers:

import java.util.Comparator;
import java.util.TreeMap;

public class TreeMapComparators {
    public static void main(String[] args) {
        TreeMap<Integer, String> desc = new TreeMap<>(Comparator.reverseOrder());
        desc.put(3, "bronze");
        desc.put(1, "gold");
        desc.put(2, "silver");
        System.out.println("Reverse order:    " + desc);

        TreeMap<String, String> headers = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
        headers.put("Content-Type", "text/html");
        headers.put("ACCEPT", "*/*");
        System.out.println("Case-insensitive: get(content-type) = " + headers.get("content-type"));
        System.out.println("                  get(accept)       = " + headers.get("accept"));
    }
}

Reverse order:    {3=bronze, 2=silver, 1=gold}
Case-insensitive: get(content-type) = text/html
                  get(accept)       = */*

6. Navigation Methods

Because keys are sorted, TreeMap can answer "what comes before or after X?" and "what lies between X and Y?" quickly. Here a day's events are keyed by time (as hhmm numbers):

import java.util.TreeMap;

public class TreeMapNavigation {
    public static void main(String[] args) {
        TreeMap<Integer, String> events = new TreeMap<>();
        events.put(900, "stand-up");
        events.put(1100, "design review");
        events.put(1300, "lunch");
        events.put(1600, "demo");

        System.out.println("floorKey(1200):     " + events.floorKey(1200));
        System.out.println("ceilingEntry(1200): " + events.ceilingEntry(1200));
        System.out.println("lowerKey(900):      " + events.lowerKey(900));
        System.out.println("higherEntry(1300):  " + events.higherEntry(1300));

        System.out.println("headMap(1300):      " + events.headMap(1300));          // keys < 1300
        System.out.println("tailMap(1300):      " + events.tailMap(1300));          // keys >= 1300
        System.out.println("subMap(1000, 1500): " + events.subMap(1000, 1500));
        System.out.println("descendingMap():    " + events.descendingMap());

        System.out.println("pollFirstEntry():   " + events.pollFirstEntry() + " -> " + events.keySet());
    }
}

floorKey(1200):     1100
ceilingEntry(1200): 1300=lunch
lowerKey(900):      null
higherEntry(1300):  1600=demo
headMap(1300):      {900=stand-up, 1100=design review}
tailMap(1300):      {1300=lunch, 1600=demo}
subMap(1000, 1500): {1100=design review, 1300=lunch}
descendingMap():    {1600=demo, 1300=lunch, 1100=design review, 900=stand-up}
pollFirstEntry():   900=stand-up -> [1100, 1300, 1600]

All the "lookup" methods return null when no key qualifies, and all range methods return live views backed by the map.

7. Practical Example: Range Lookup with floorEntry()

Store the start of each band as the key. floorEntry(x) then returns the band that x falls into. The same pattern works for tax slabs, shipping rates, discount tiers and IP ranges.

import java.util.TreeMap;

public class GradeLookup {
    // Lower bound of each grade -> grade
    private static final TreeMap<Integer, String> GRADES = new TreeMap<>();
    static {
        GRADES.put(0, "F");
        GRADES.put(40, "D");
        GRADES.put(55, "C");
        GRADES.put(70, "B");
        GRADES.put(85, "A");
    }

    static String grade(int marks) {
        return GRADES.floorEntry(marks).getValue();   // highest band whose start <= marks
    }

    public static void main(String[] args) {
        for (int m : new int[] {12, 40, 68, 85, 99}) {
            System.out.println(m + " marks -> grade " + grade(m));
        }
    }
}

12 marks -> grade F
40 marks -> grade D
68 marks -> grade C
85 marks -> grade A
99 marks -> grade A

8. Practical Example: Sorted Word Count

Counting with a TreeMap gives you the result already sorted by key:

import java.util.Map;
import java.util.TreeMap;

public class SortedWordCount {
    public static void main(String[] args) {
        String text = "to be or not to be that is the question";

        Map<String, Integer> counts = new TreeMap<>();   // keys come out alphabetically
        for (String w : text.split(" ")) {
            counts.merge(w, 1, Integer::sum);
        }
        counts.forEach((word, n) -> System.out.println(word + ": " + n));
    }
}

be: 2
is: 1
not: 1
or: 1
question: 1
that: 1
the: 1
to: 2

9. How TreeMap Works Internally

TreeMap is a red-black tree: a binary search tree in which every node stores a key, a value, links to its left child, right child and parent, and a colour (red or black).

• For any node, keys in its left subtree are smaller and keys in its right subtree are larger.
• get(k) starts at the root and moves left or right after each comparison.
• After every insert or delete, rotations and recolouring keep the tree balanced, so its height stays O(log n). A million keys need only about 20 to 40 comparisons.
• Iteration performs an in-order walk, which visits keys in sorted order.
• The first put() calls compare(key, key) to check that the key type is comparable (and not null).

10. Time Complexity

11. TreeMap vs HashMap vs LinkedHashMap

12. Thread Safety

TreeMap is not synchronized. For a sorted map shared between threads, use ConcurrentSkipListMap, which implements the same NavigableMap interface. Collections.synchronizedSortedMap(new TreeMap<>()) is the simpler but less scalable alternative.

13. Common Mistakes

• Keys that are not Comparable and no comparator: ClassCastException.
• Putting a null key: NullPointerException.
• A comparator that returns 0 for different keys: values are overwritten silently.
• Changing a key's sort fields after inserting it: the tree becomes inconsistent.
• Calling firstKey() on an empty map: NoSuchElementException; use firstEntry(), which returns null.
• Using TreeMap when order is not needed: HashMap is faster.

14. Summary

• TreeMap stores entries sorted by key in a red-black tree.
• Basic operations are O(log n); iteration is in key order.
• Keys need natural ordering or a comparator, and a null key is not allowed.
• Navigation methods make nearest-key and range lookups simple.
• Use ConcurrentSkipListMap for a thread-safe sorted map.

Related Tutorials

• SortedMap in Java
• NavigableMap in Java
• HashMap in Java
• TreeSet in Java
• Difference between HashMap and TreeMap

Reference: Java SE 21 API: java.util.TreeMap

Frequently Asked Questions (FAQ)