TreeMap in Java

Introduction

TreeMap is a class in Java that stores data in the form of key-value pairs and keeps its entries sorted according to the keys.

It is part of the Java Collections Framework and implements the NavigableMap interface.

Unlike HashMap, which does not guarantee any particular ordering, TreeMap maintains its keys in ascending order by default.

Example

import java.util.TreeMap;
 
public class HelloWorld {
    public static void main(String[] args) {
 
        TreeMap<Integer, String> students = new TreeMap<>();
 
        students.put(103, "Rahul");
        students.put(101, "Amit");
        students.put(102, "Priya");
 
        System.out.println(students);
    }
}

Output

{101=Amit, 102=Priya, 103=Rahul}

Notice that the entries are displayed according to the sorted order of their keys.

What is TreeMap?

TreeMap is a map implementation that stores entries in sorted order based on their keys.

The basic structure is:

Key → Value

For example:

101 → Amit
102 → Priya
103 → Rahul

The keys are automatically maintained in sorted order.

TreeMap Hierarchy

The basic hierarchy of TreeMap is:

Map
  ↓
SortedMap
  ↓
NavigableMap
  ↓
TreeMap

TreeMap implements the NavigableMap interface.

It is declared as:

public class TreeMap<K, V>
        extends AbstractMap<K, V>
        implements NavigableMap<K, V>, Cloneable, Serializable

Here:

• K represents the key type.
• V represents the value type.

For example:

TreeMap<Integer, String> map;

Here:

• Integer is the key type.
• String is the value type.

Creating a TreeMap

You can create a TreeMap using its constructor.

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

You can also create it using the Map interface:

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

This is useful when you want to program against the interface rather than the implementation.

Adding Elements to TreeMap

The put() method is used to add key-value pairs.

import java.util.TreeMap;
 
public class HelloWorld {
    public static void main(String[] args) {
 
        TreeMap<Integer, String> map = new TreeMap<>();
 
        map.put(3, "Java");
        map.put(1, "Python");
        map.put(2, "C++");
 
        System.out.println(map);
    }
}

Output

{1=Python, 2=C++, 3=Java}

Although the values were inserted in the order 3, 1, 2, the keys are displayed in sorted order.

TreeMap Does Not Allow Duplicate Keys

A map cannot contain duplicate keys.

If you insert the same key again, the existing value is replaced.

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(101, "Amit");
map.put(102, "Rahul");
 
map.put(101, "Priya");
 
System.out.println(map);

Output

{101=Priya, 102=Rahul}

The key 101 already existed, so its value was changed from "Amit" to "Priya".

TreeMap Allows Duplicate Values

TreeMap allows multiple keys to have the same value.

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(101, "Java");
map.put(102, "Java");
map.put(103, "Python");
 
System.out.println(map);

Output

{101=Java, 102=Java, 103=Python}

The values can be duplicated because only the keys must be unique.

Accessing Values

The get() method is used to retrieve a value using its key.

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(101, "Amit");
map.put(102, "Rahul");
 
System.out.println(map.get(101));

Output

Amit

If the specified key does not exist, get() returns null.

System.out.println(map.get(105));

Output:

null

Checking Whether a Key Exists

The containsKey() method checks whether a particular key exists.

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(101, "Amit");
map.put(102, "Rahul");
 
System.out.println(map.containsKey(101));
System.out.println(map.containsKey(105));

Output

true
false

Checking Whether a Value Exists

The containsValue() method checks whether a value exists.

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(101, "Amit");
map.put(102, "Rahul");
 
System.out.println(map.containsValue("Rahul"));

Output

true

Removing an Entry

The remove() method removes an entry using its key.

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(101, "Amit");
map.put(102, "Rahul");
map.put(103, "Priya");
 
map.remove(102);
 
System.out.println(map);

Output

{101=Amit, 103=Priya}

Getting the First Key

The firstKey() method returns the smallest key.

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(30, "C");
map.put(10, "A");
map.put(20, "B");
 
System.out.println(map.firstKey());

Output

10

Getting the Last Key

The lastKey() method returns the largest key.

System.out.println(map.lastKey());

Output:

30

Getting the First Entry

The firstEntry() method returns the entry with the smallest key.

System.out.println(map.firstEntry());

Output:

10=A

Getting the Last Entry

The lastEntry() method returns the entry with the largest key.

System.out.println(map.lastEntry());

Output:

30=C

Navigating Through TreeMap

One of the important advantages of TreeMap is that it provides methods for navigating around keys.

lowerKey()

Returns the greatest key that is strictly less than the specified key.

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(10, "A");
map.put(20, "B");
map.put(30, "C");
 
System.out.println(map.lowerKey(25));

Output:

20

higherKey()

Returns the smallest key that is strictly greater than the specified key.

System.out.println(map.higherKey(25));

Output:

30

floorKey()

Returns the greatest key that is less than or equal to the specified key.

System.out.println(map.floorKey(20));

Output:

20

If the key does not exist:

System.out.println(map.floorKey(25));

Output:

20

ceilingKey()

Returns the smallest key that is greater than or equal to the specified key.

System.out.println(map.ceilingKey(25));

Output:

30

These methods are useful when you need to find nearby keys.

Iterating Over TreeMap

You can iterate over a TreeMap using entrySet().

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(103, "Rahul");
map.put(101, "Amit");
map.put(102, "Priya");
 
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

Output

101 = Amit
102 = Priya
103 = Rahul

The entries are automatically traversed according to key order.

Iterating Over Keys

You can use keySet() to iterate through the keys.

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

Output:

101
102
103

Iterating Over Values

You can use values() to iterate through the values.

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

Descending Order

By default, TreeMap stores keys in ascending order.

You can obtain a reverse-order view using descendingMap().

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(10, "A");
map.put(20, "B");
map.put(30, "C");
 
System.out.println(map.descendingMap());

Output

{30=C, 20=B, 10=A}

You can also use:

map.descendingKeySet();

to obtain the keys in descending order.

Using a Comparator with TreeMap

By default, TreeMap uses the natural ordering of keys.

You can provide a Comparator when creating the TreeMap to define a different ordering.

TreeMap<Integer, String> map =
        new TreeMap<>(Comparator.reverseOrder());
 
map.put(10, "A");
map.put(20, "B");
map.put(30, "C");
 
System.out.println(map);

Output

{30=C, 20=B, 10=A}

Here, the keys are maintained in descending order.

TreeMap with String Keys

TreeMap can also use strings as keys.

TreeMap<String, Integer> map = new TreeMap<>();
 
map.put("Java", 10);
map.put("Python", 20);
map.put("C++", 30);
 
System.out.println(map);

The keys are ordered according to their natural string ordering.

Null Keys in TreeMap

A standard TreeMap does not permit a null key when using its natural ordering.

For example:

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(null, "A");

This results in a NullPointerException.

However, whether null keys can be handled depends on the comparator used. For general use, it is best to avoid null keys in TreeMap.

TreeMap can contain null values.

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(101, null);
 
System.out.println(map);

This is allowed.

TreeMap Size

The size() method returns the number of entries.

System.out.println(map.size());

Checking Whether TreeMap Is Empty

Use isEmpty().

if (map.isEmpty()) {
    System.out.println("TreeMap is empty");
}

Removing All Entries

The clear() method removes all entries.

map.clear();

After calling clear(), the TreeMap becomes empty.

SubMap

TreeMap provides methods for working with a range of keys.

The subMap() method returns a portion of the map.

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(10, "A");
map.put(20, "B");
map.put(30, "C");
map.put(40, "D");
 
System.out.println(map.subMap(20, 40));

Output:

{20=B, 30=C}

The default range includes the first key and excludes the second key.

headMap()

headMap() returns entries whose keys are smaller than the specified key.

System.out.println(map.headMap(30));

Output:

{10=A, 20=B}

tailMap()

tailMap() returns entries whose keys are greater than or equal to the specified key.

System.out.println(map.tailMap(30));

Output:

{30=C, 40=D}

TreeMap vs HashMap

Both TreeMap and HashMap store key-value pairs, but they behave differently.

TreeMap vs LinkedHashMap

LinkedHashMap maintains insertion order, while TreeMap maintains sorted key order.

For example:

LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
 
map.put(30, "C");
map.put(10, "A");
map.put(20, "B");

The iteration order is:

30
10
20

With TreeMap:

TreeMap<Integer, String> map = new TreeMap<>();
 
map.put(30, "C");
map.put(10, "A");
map.put(20, "B");

The iteration order is:

10
20
30

So:

HashMap       → No guaranteed order
LinkedHashMap → Insertion order
TreeMap       → Sorted key order

Time Complexity of TreeMap

TreeMap is generally implemented using a Red-Black Tree, which is a self-balancing binary search tree.

For basic operations:

The logarithmic complexity comes from keeping the underlying tree balanced.

When Should You Use TreeMap?

TreeMap is useful when you need:

• Key-value storage.
• Keys maintained in sorted order.
• Navigation between nearby keys.
• Range-based operations.
• First and last key access.
• Ascending or descending traversal.
• floor, ceiling, lower, and higher operations.

For example, if you need to find the closest key that is less than or greater than a given value, TreeMap provides these operations directly.

Complete TreeMap Example

import java.util.Map;
import java.util.TreeMap;
 
public class HelloWorld {
 
    public static void main(String[] args) {
 
        TreeMap<Integer, String> students = new TreeMap<>();
 
        students.put(103, "Rahul");
        students.put(101, "Amit");
        students.put(102, "Priya");
        students.put(104, "Neha");
 
        System.out.println("Students: " + students);
 
        System.out.println("First Key: " + students.firstKey());
        System.out.println("Last Key: " + students.lastKey());
 
        System.out.println("Lower Key: " + students.lowerKey(103));
        System.out.println("Higher Key: " + students.higherKey(103));
 
        System.out.println("Floor Key: " + students.floorKey(103));
        System.out.println("Ceiling Key: " + students.ceilingKey(103));
 
        System.out.println("\nIterating:");
 
        for (Map.Entry<Integer, String> entry : students.entrySet()) {
            System.out.println(
                entry.getKey() + " = " + entry.getValue()
            );
        }
    }
}

Output

Students: {101=Amit, 102=Priya, 103=Rahul, 104=Neha}
First Key: 101
Last Key: 104
Lower Key: 102
Higher Key: 104
Floor Key: 103
Ceiling Key: 103
 
Iterating:
101 = Amit
102 = Priya
103 = Rahul
104 = Neha

Key Points to Remember

• TreeMap stores data as key-value pairs.
• It implements the NavigableMap interface.
• Keys are maintained in sorted order by default.
• Keys must be unique.
• Duplicate keys replace their existing values.
• Duplicate values are allowed.
• TreeMap is generally based on a Red-Black Tree.
• Basic search, insertion, and deletion operations generally take O(log n) time.
• firstKey() returns the smallest key.
• lastKey() returns the largest key.
• lowerKey() finds the closest smaller key.
• higherKey() finds the closest larger key.
• floorKey() finds the closest key less than or equal to the given key.
• ceilingKey() finds the closest key greater than or equal to the given key.
• descendingMap() provides a reverse-order view.
• A Comparator can be supplied to customize key ordering.
• TreeMap is useful when sorted data and navigation are required.