TreeMap in Java

TreeMap is a widely used Map implementation in Java that stores key-value pairs in sorted order.

It is part of the java.util package and implements the SortedMap interface.

What is TreeMap in Java?

A TreeMap is a Red-Black Tree based implementation of Map that:

• Stores data as key → value pairs
• Maintains keys in sorted order (natural ordering or custom comparator)
• Does NOT allow null keys (but allows multiple null values)
• Provides logarithmic time (O(log n)) performance for most operations
• Is not synchronized / thread-safe

Package:

import java.util.TreeMap;

Where TreeMap Fits in the Collection Framework

Iterable (Not parent)
   └── Collection (Not parent)
Map
   └── SortedMap
         └── TreeMap

TreeMap implements:

• Map
• NavigableMap
• Cloneable
• Serializable

Internal Data Structure:

• Red-Black Tree (Self-balancing binary search tree)

Key Features of TreeMap

• Maintains sorted order of keys
• Provides O(log n) lookup, insertion, and deletion
• Does not allow null keys
• Allows null values
• Implements NavigableMap → supports methods like firstKey(), lastKey(), headMap(), tailMap(), etc.

Creating a TreeMap in Java

1. Default TreeMap

Creates an empty TreeMap with keys sorted in natural ascending order.

TreeMap<Integer, String> map = new TreeMap<>();

2. With Custom Comparator

Creates a TreeMap with custom sorting order as per the comparator.

TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder());

3. From Another Map

Creates a TreeMap by copying entries from an existing map, with keys sorted automatically.

Map<Integer, String> existingMap = new HashMap<>();
TreeMap<Integer, String> map = new TreeMap<>(existingMap);

Common TreeMap Methods

1. Add & Update Methods

put(K key, V value) – Adds or updates a key-value pair

map.put(1, "Java");
map.put(2, "Python");

putIfAbsent(K key, V value) – Adds only if key is not present

map.putIfAbsent(3, "C++");

putAll(Map m) – Copies all entries from another map

map.putAll(otherMap);

2. Search / Check Methods

get(Object key) – Returns the value for a given key

map.get(1);

containsKey(Object key) – Checks if key exists

map.containsKey(2);

containsValue(Object value) – Checks if value exists

map.containsValue("Java");

firstKey() / lastKey() – Returns first/last key

map.firstKey();
map.lastKey();

size() / isEmpty() – Returns number of entries / checks if empty

map.size();
map.isEmpty();

3. Remove Methods

remove(Object key) – Removes mapping for key

map.remove(2);

clear() – Removes all entries

map.clear();

4. Navigation / Submap Methods

headMap(K toKey) – Returns keys less than toKey

map.headMap(3);

tailMap(K fromKey) – Returns keys greater than or equal to fromKey

map.tailMap(2);

subMap(K fromKey, K toKey) – Returns keys in the range

map.subMap(1, 3);

ceilingKey(K key) / floorKey(K key) – Smallest key ≥ / largest key ≤ given key

map.ceilingKey(2);
map.floorKey(2);

higherKey(K key) / lowerKey(K key) – Next higher / lower key

map.higherKey(1);
map.lowerKey(2);

5. Iteration Methods

keySet() – Returns all keys

for (Integer key : map.keySet()) {
    System.out.println(key);
}

values() – Returns all values

for (String value : map.values()) {
    System.out.println(value);
}

entrySet() – Returns key-value pairs

for (Map.Entry<Integer, String> e : map.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}

Time Complexity of TreeMap

TreeMap vs HashMap vs LinkedHashMap

Advantages of TreeMap

• Maintains sorted order
• Supports range queries
• NavigableMap provides extra methods for navigation
• Safer than manually sorting HashMap

Disadvantages of TreeMap

• Slower than HashMap / LinkedHashMap (O(log n) vs O(1))
• Cannot store null keys
• Slightly more memory consumption due to tree structure

Example Program

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

public class Main {
    public static void main(String[] args) {

        TreeMap<Integer, String> map = new TreeMap<>();

        map.put(101, "Java");
        map.put(102, "Python");
        map.put(103, "C++");

        for (Map.Entry<Integer, String> e : map.entrySet()) {
            System.out.println(e.getKey() + " = " + e.getValue());
        }
    }
}

Output:

101 = Java
102 = Python
103 = C++

Real-World Use Cases

• Storing sorted data
• Implementing leaderboards / ranking systems
• Performing range queries
• Maintaining naturally ordered maps
• Database indexing or Tree-based caches

Points to Remember About TreeMap

• TreeMap stores key–value pairs in sorted order (natural or custom comparator).
• Does NOT allow null keys, but allows multiple null values.
• Implements Map, NavigableMap, Cloneable, Serializable.
• Uses Red-Black Tree internally for O(log n) operations.
• Fast search, insertion, deletion (O(log n)) but slower than HashMap (O(1) average).
• Provides navigation methods: firstKey(), lastKey(), ceilingKey(), floorKey(), headMap(), tailMap(), subMap().
• Ideal for sorted maps, range queries, leaderboard or ranking systems.
• Not thread-safe; use Collections.synchronizedSortedMap() or ConcurrentSkipListMap if needed.
• Supports iteration over keys, values, and entries in sorted order.
• Use custom Comparator to define non-natural sorting order.