Java TreeMap

The TreeMap class in Java is part of the Java Collection Framework and implements the Map and SortedMap interfaces. It stores key-value pairs in sorted order based on the natural ordering of keys or by a custom comparator.

What is TreeMap?#

A TreeMap is a Red-Black Tree-based implementation of the NavigableMap interface. It automatically keeps the keys in sorted ascending order.

It implements:#

• Map Interface – Stores key-value pairs.
• SortedMap Interface – Maintains keys in sorted order.

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

Here TreeMap implements NavigableMap and NavigableMap extends SortedMap, therefore TreeMap indirectly implements SortedMap interface.

SortedMap Interface#

SortedMap is a subinterface of Map that provides additional methods for dealing with sorted keys. A TreeMap uses this interface to keep its keys automatically sorted in natural order (or using a custom comparator).

public interface SortedMap<K, V> extends Map<K, V> {
    Comparator<? super K> comparator();
    K firstKey();
    K lastKey();
    SortedMap<K, V> headMap(K toKey);
    SortedMap<K, V> tailMap(K fromKey);
    SortedMap<K, V> subMap(K fromKey, K toKey);
}

Characteristics of TreeMap:#

• Stores data as key-value pairs.
• Maintains keys in ascending sorted order.
• Does not allow null keys (throws NullPointerException).
• Allows multiple null values.
• Not thread-safe (must be synchronized externally if used in multi-threaded environment).
• Slower than HashMap and LinkedHashMap due to sorting overhead.

TreeMap Syntax#

TreeMap<KeyType, ValueType> mapName = new TreeMap<>();

Commonly Used Methods#

Example: Basic TreeMap#

import java.util.*;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(3, "Banana");
        map.put(1, "Apple");
        map.put(2, "Mango");

        System.out.println("TreeMap: " + map);
    }
}

Output:

TreeMap: {1=Apple, 2=Mango, 3=Banana}

Explanation#

The keys are automatically sorted in ascending order.

Example: Using firstKey(), lastKey(), headMap(), tailMap(), subMap()#

import java.util.*;

public class TreeMapMethods {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(100, "Hundred");
        map.put(50, "Fifty");
        map.put(150, "One Fifty");
        map.put(75, "Seventy Five");

        System.out.println("Original Map: " + map);
        System.out.println("First Key: " + map.firstKey());
        System.out.println("Last Key: " + map.lastKey());
        System.out.println("Head Map (toKey=100): " + map.headMap(100));
        System.out.println("Tail Map (fromKey=100): " + map.tailMap(100));
        System.out.println("Sub Map (50 to 150): " + map.subMap(50, 150));
    }
}

Output:

Original Map: {50=Fifty, 75=Seventy Five, 100=Hundred, 150=One Fifty}
First Key: 50
Last Key: 150
Head Map (toKey=100): {50=Fifty, 75=Seventy Five}
Tail Map (fromKey=100): {100=Hundred, 150=One Fifty}
Sub Map (50 to 150): {50=Fifty, 75=Seventy Five, 100=Hundred}

Performance#

TreeMap operations are slower than HashMap and LinkedHashMap because they require maintaining sorting order via a Red-Black Tree.

When to Use TreeMap#

• When sorted ordering of keys is required.
• When you need range-based queries like subMap(), headMap(), etc.
• When you don't care about insertion order.

Conclusion#

In this blog, we covered the TreeMap class in Java in detail. We explored its key features, performance, and examples of important methods like put(), get(), firstKey(), headMap(), tailMap(), and more. We also looked at how TreeMap implements the SortedMap interface to maintain sorted key order. Use TreeMap when you need sorted data, and are okay with the performance trade-offs compared to HashMap or LinkedHashMap.