TreeMap in Java

TreeMap in Java is a class that implements NavigableMap and stores key-value pairs sorted by key. It is used when you need the keys in order, or need to find keys near a given value. Inside, it uses a red-black tree, a self-balancing binary search tree, so put, get and remove take O(log n) time. In this lesson, you will learn how to create a TreeMap, sort its keys in natural or custom order, and choose between TreeMap and HashMap.

Declaration

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

Features of TreeMap

• Sorted by key: natural order, or the order of a comparator.
• Unique keys, where "same key" means compareTo or the comparator returns 0.
• No null keys; null values are allowed.
• O(log n) put, get, remove and containsKey.
• Navigable: floorKey, ceilingEntry, headMap, tailMap and more.
• Not synchronized.

Constructors

Example: Keys Always Sorted

Let's see an example where the keys are added in mixed order.

import java.util.TreeMap;
 
public class TreeMapDemo {
    public static void main(String[] args) {
        TreeMap<String, Integer> marks = new TreeMap<>();
        marks.put("Srihitha", 78);
        marks.put("Navika", 91);
        marks.put("Advitha", 85);
        marks.put("Anamaneni", 66);
        System.out.println(marks);
 
        System.out.println("First: " + marks.firstKey());
        System.out.println("Last: " + marks.lastEntry());
        System.out.println("After Advitha: " + marks.higherKey("Advitha"));
 
        System.out.println(String.join(" ", marks.descendingKeySet()));
    }
}

{Advitha=85, Anamaneni=66, Navika=91, Srihitha=78}
First: Advitha
Last: Srihitha=78
After Advitha: Anamaneni
Srihitha Navika Anamaneni Advitha

Explanation: The map prints its keys alphabetically, whatever the insertion order. firstKey, lastEntry and higherKey work because the keys are sorted. descendingKeySet returns the keys in reverse order, and String.join puts spaces between them.

Example: Custom Key Order

import java.util.Comparator;
import java.util.TreeMap;
 
public class CustomOrder {
    public static void main(String[] args) {
        TreeMap<String, Integer> byLength = new TreeMap<>(
            Comparator.comparingInt(String::length)
                      .thenComparing(Comparator.reverseOrder()));
        byLength.put("Navika", 1);
        byLength.put("Srihitha", 2);
        byLength.put("Advitha", 3);
        byLength.put("Anamaneni", 4);
        System.out.println(byLength);
 
        TreeMap<String, Integer> ignoreCase =
            new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
        ignoreCase.put("navika", 1);
        ignoreCase.put("NAVIKA", 2);
        System.out.println(ignoreCase);
    }
}

{Navika=1, Advitha=3, Srihitha=2, Anamaneni=4}
{navika=2}

Explanation: The first map sorts keys by length, and names of equal length in reverse alphabetical order. The second compares keys ignoring case, so "NAVIKA" counts as the same key as "navika": the original key is kept and its value is replaced by 2.

TreeMap vs HashMap

Common Mistakes

Putting a null key. It throws NullPointerException.

Using keys that aren't Comparable without a comparator. The first put throws ClassCastException.

Choosing TreeMap when order doesn't matter. HashMap is faster.

Interview Corner

Practice

1. Easy: Count the words in a sentence with a TreeMap<String, Integer> and print them alphabetically.
2. Harder: Store dates (LocalDate) of exams in a TreeMap and print the next exam after today using ceilingEntry.

Key Takeaways