JavaData StructuresIntermediate

TreeMap

A Red-Black tree based implementation of the NavigableMap interface, providing sorted key-value pairs and guaranteed log(n) time complexity for basic operations.

Review the syntaxStudy the examplesOpen the coding app
new TreeMap<K, V>()
new TreeMap<K, V>(Comparator<? super K> comparator)
Open Coding Reference

This static page keeps the syntax and examples indexed for search, while the coding app handles interactive exploration and saved references.

What it does

Overview

A Red-Black tree based implementation of the NavigableMap interface, providing sorted key-value pairs and guaranteed log(n) time complexity for basic operations.

A `TreeMap` in Java is a sorted map implementation that stores its entries in ascending key order, according to the natural ordering of its keys, or by a `Comparator` provided at map creation time. It is backed by a Red-Black tree, a self-balancing binary search tree, which guarantees O(log n) time complexity for `put()`, `get()`, `remove()`, and `containsKey()` operations. This logarithmic performance makes `TreeMap` suitable for applications where sorted data is crucial, such as maintaining sorted lists of items, implementing dictionaries, or performing range queries. Unlike `HashMap`, `TreeMap` does not allow `null` keys (as they cannot be naturally ordered or compared by a `Comparator`), but it does allow `null` values. `TreeMap` also offers additional methods from the `NavigableMap` interface, like `firstEntry()`, `lastEntry()`, `floorEntry()`, `ceilingEntry()`, which leverage its sorted nature. It is not thread-safe; for concurrent access, `ConcurrentSkipListMap` or `Collections.synchronizedSortedMap()` should be used. When choosing between `HashMap` and `TreeMap`, the primary consideration is whether you need sorted keys and guaranteed logarithmic performance, or if average constant time performance is sufficient without ordering.

Quick reference

Syntax

new TreeMap<K, V>()
new TreeMap<K, V>(Comparator<? super K> comparator)

Inputs

Parameters

comparator (optional)Comparator<? super K> · The comparator that will be used to order this map. If null, the natural ordering of the keys will be used.

See it in practice

Examples

1

Basic TreeMap with natural ordering

import java.util.TreeMap;

TreeMap<String, Integer> studentScores = new TreeMap<>();
studentScores.put("Alice", 95);
studentScores.put("Charlie", 88);
studentScores.put("Bob", 92);

System.out.println("Student scores (sorted by name): " + studentScores);
Output:
Student scores (sorted by name): {Alice=95, Bob=92, Charlie=88}

Elements are automatically sorted by their String keys in natural (alphabetical) order.

2

TreeMap with custom Comparator (reverse order)

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

TreeMap<String, Integer> reverseScores = new TreeMap<>(Comparator.reverseOrder());
reverseScores.put("Alice", 95);
reverseScores.put("Charlie", 88);
reverseScores.put("Bob", 92);

System.out.println("Student scores (reverse sorted by name): " + reverseScores);
Output:
Student scores (reverse sorted by name): {Charlie=88, Bob=92, Alice=95}

A `Comparator` is provided to sort keys in reverse alphabetical order.

3

Using NavigableMap methods

import java.util.TreeMap;

TreeMap<Integer, String> codes = new TreeMap<>();
codes.put(100, "Continue");
codes.put(200, "OK");
codes.put(300, "Redirect");
codes.put(404, "Not Found");
codes.put(500, "Internal Error");

System.out.println("First entry: " + codes.firstEntry());
System.out.println("Entry <= 200: " + codes.floorEntry(200));
System.out.println("Entry >= 400: " + codes.ceilingEntry(400));
System.out.println("Submap from 200 (inclusive) to 400 (exclusive): " + codes.subMap(200, 400));
Output:
First entry: 100=Continue Entry <= 200: 200=OK Entry >= 400: 404=Not Found Submap from 200 (inclusive) to 400 (exclusive): {200=OK, 300=Redirect}

Demonstrates `NavigableMap` methods like `firstEntry()`, `floorEntry()`, `ceilingEntry()`, and `subMap()` for efficient range queries and access to specific elements based on their sorted order.

Debug faster

Common Errors

1

NullPointerException with null keys

Cause: `TreeMap` does not allow `null` keys because it relies on key comparison (either natural ordering or a `Comparator`) to maintain its sorted structure. A `null` key cannot be compared.

Fix: Ensure that keys inserted into a `TreeMap` are never `null`. If `null` keys are a possibility, consider using `HashMap` if ordering is not critical, or handle `null` keys explicitly before insertion.

import java.util.TreeMap;

TreeMap<String, String> map = new TreeMap<>();
// map.put(null, "value"); // Throws NullPointerException

// Correct:
map.put("key", "value");
System.out.println(map);

Runtime support

Compatibility

JVMN/AJava 1.2+

Source: Oracle Java Documentation

Common questions

Frequently Asked Questions

A Red-Black tree based implementation of the NavigableMap interface, providing sorted key-value pairs and guaranteed log(n) time complexity for basic operations.

comparator: The comparator that will be used to order this map. If null, the natural ordering of the keys will be used.

NullPointerException with null keys: Ensure that keys inserted into a `TreeMap` are never `null`. If `null` keys are a possibility, consider using `HashMap` if ordering is not critical, or handle `null` keys explicitly before insertion.