Java TreeMap

A TreeMap is a NavigableMap implementation that stores key-value pairs sorted by keys using a Red-Black tree. It provides O(log n) time for get, put, and remove operations.

Key Characteristics

Creating a TreeMap

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

// Natural ordering (keys must implement Comparable)
TreeMap<String, Integer> scores = new TreeMap<>();

// Custom comparator (reverse order)
TreeMap<String, Integer> descending = new TreeMap<>(
    Comparator.reverseOrder()
);

// Case-insensitive keys
TreeMap<String, String> caseInsensitive = new TreeMap<>(
    String.CASE_INSENSITIVE_ORDER
);

// From existing map
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("banana", 2);
hashMap.put("apple", 1);
TreeMap<String, Integer> sorted = new TreeMap<>(hashMap);
// Keys sorted: apple, banana

Click Run to execute your code

NavigableMap Methods

TreeMap provides powerful navigation for finding entries by key:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "Ten");
map.put(20, "Twenty");
map.put(30, "Thirty");
map.put(40, "Forty");
map.put(50, "Fifty");

// First and last
Map.Entry<Integer, String> first = map.firstEntry(); // 10=Ten
Map.Entry<Integer, String> last = map.lastEntry();   // 50=Fifty
Integer firstKey = map.firstKey();  // 10
Integer lastKey = map.lastKey();    // 50

// Floor/Ceiling entries (closest)
Map.Entry<Integer, String> floor = map.floorEntry(25);   // 20=Twenty (<=25)
Map.Entry<Integer, String> ceiling = map.ceilingEntry(25); // 30=Thirty (>=25)
Map.Entry<Integer, String> lower = map.lowerEntry(30);   // 20=Twenty (<30)
Map.Entry<Integer, String> higher = map.higherEntry(30); // 40=Forty (>30)

// Polling (retrieve and remove)
Map.Entry<Integer, String> pollFirst = map.pollFirstEntry(); // Removes 10
Map.Entry<Integer, String> pollLast = map.pollLastEntry();   // Removes 50

// Submaps (views, backed by original)
SortedMap<Integer, String> head = map.headMap(30);      // {20=Twenty}
SortedMap<Integer, String> tail = map.tailMap(30);      // {30=Thirty, 40=Forty}
SortedMap<Integer, String> sub = map.subMap(20, 40);    // {20=Twenty, 30=Thirty}

// Inclusive bounds
NavigableMap<Integer, String> inc = map.subMap(20, true, 40, true);

// Descending view
NavigableMap<Integer, String> desc = map.descendingMap();

Common Use Cases

// 1. Time-based data (sorted by timestamp)
TreeMap<LocalDateTime, String> events = new TreeMap<>();
events.put(LocalDateTime.now(), "Event A");
events.put(LocalDateTime.now().plusHours(1), "Event B");
// Get events after a certain time
SortedMap<LocalDateTime, String> future = events.tailMap(LocalDateTime.now());

// 2. Price lookup (find nearest price tier)
TreeMap<Integer, Double> priceTiers = new TreeMap<>();
priceTiers.put(100, 0.10);   // 100+ units: $0.10 each
priceTiers.put(500, 0.08);   // 500+ units: $0.08 each
priceTiers.put(1000, 0.05);  // 1000+ units: $0.05 each

int quantity = 750;
Double rate = priceTiers.floorEntry(quantity).getValue(); // 0.08

// 3. Alphabetically sorted dictionary
TreeMap<String, String> dictionary = new TreeMap<>();
dictionary.put("apple", "a fruit");
dictionary.put("car", "a vehicle");
dictionary.put("book", "something to read");
// Iterates: apple, book, car

// 4. Score rankings with navigation
TreeMap<Integer, List<String>> rankings = new TreeMap<>(
    Comparator.reverseOrder()  // Highest first
);
// Get top 3 scores
rankings.entrySet().stream().limit(3).forEach(System.out::println);

Thread Safety

// TreeMap is NOT thread-safe. For concurrent access:

// Option 1: Synchronized wrapper
Map<String, Integer> syncMap = Collections.synchronizedSortedMap(
    new TreeMap<>()
);

// Option 2: ConcurrentSkipListMap (better performance)
ConcurrentNavigableMap<String, Integer> concurrentMap =
    new ConcurrentSkipListMap<>();

Summary