Java TreeMap

TreeMap is a Map implementation that stores its key-value entries in a self-balancing tree, keeping the entries sorted by key at all times.

In this page:

Introduction to TreeMap
Automatic Key Sorting
Adding and Removing Entries
Navigation Methods
Custom Sort Order with Comparator

Syntax

java

TreeMap<KeyType, ValueType> map = new TreeMap<>();
map.put(key, value);  // sorted by key
map.firstKey();

Introduction to TreeMap

TreeMap is an implementation of the Map interface that stores its key-value entries in a red-black tree, keeping the entries sorted by key at all times rather than in insertion or hash order.

Example: Introduction to TreeMap

java

import java.util.TreeMap;
public class Main {
	public static void main(String[] args) {
		TreeMap<String, Integer> map = new TreeMap<>(); // red-black tree, sorted by key
		map.put("banana", 1);
		map.put("apple", 2);
		System.out.println(map);
	}
}

Automatic Key Sorting

Entries added to a TreeMap are automatically kept sorted by their key's natural ordering -- numeric keys sort numerically and String keys sort alphabetically -- regardless of the order they were inserted in.

Example: Automatic Key Sorting

java

import java.util.TreeMap;
public class Main {
	public static void main(String[] args) {
		TreeMap<Integer, String> map = new TreeMap<>();
		map.put(3, "c");
		map.put(1, "a");
		map.put(2, "b");
		System.out.println(map); // sorted by key: 1, 2, 3
	}
}

Adding and Removing Entries

TreeMap supports the same put, get, and remove operations as any other Map, but every insertion or removal also re-balances the underlying tree to keep the key order intact, and putting an existing key still overwrites its value.

Example: Adding and Removing Entries

java

import java.util.TreeMap;
public class Main {
	public static void main(String[] args) {
		TreeMap<String, Integer> map = new TreeMap<>();
		map.put("apple", 3);
		map.put("apple", 5); // overwrites
		map.remove("apple");
		System.out.println(map);
	}
}

Navigation Methods

TreeMap adds navigation methods beyond a plain Map, like firstKey, lastKey, higherKey, and floorKey, which use the guaranteed sort order to efficiently find the smallest, largest, or nearest keys relative to a given value.

Example: Navigation Methods

java

// Import java.util.TreeMap so it can be used by its short name
import java.util.TreeMap;
// Define the class Main
public class Main {
	// Program entry point: the JVM starts running here
	public static void main(String[] args) {
		// Create a new TreeMap object and store it in map
		TreeMap<Integer, String> map = new TreeMap<>();
		map.put(1, "a"); map.put(5, "b"); map.put(10, "c");
		// Print a line to the console
		System.out.println(map.firstKey());
		// Print a line to the console
		System.out.println(map.lastKey());
		System.out.println(map.higherKey(5));
	}
}

Custom Sort Order with Comparator

Passing a Comparator to a TreeMap's constructor overrides the default natural key ordering, letting entries be sorted by any custom rule, such as reverse order or a computed property like key length instead of alphabetical order.

Example: Custom Sort Order with Comparator

java

import java.util.TreeMap;
import java.util.Collections;
public class Main {
	public static void main(String[] args) {
		TreeMap<Integer, String> map = new TreeMap<>(Collections.reverseOrder());
		map.put(1, "a");
		map.put(5, "b");
		System.out.println(map); // reverse sorted
	}
}

Chapter Quiz — Complete all 17 topics to unlock

0/17 topics done

Complete these topics first:

← Previous Lesson Java Set Interface Next Lesson → Java LinkedHashMap

Java TreeMap

Introduction to TreeMap

Automatic Key Sorting

Adding and Removing Entries

Navigation Methods

Custom Sort Order with Comparator

Chapter Quiz — Complete all 17 topics to unlock

Login to run this code