Topic 13718 min readStructured Tutorial

Understanding TreeMap in Java

Quick Answer

TreeMap explains treeMap is a part of Java's Collection Framework that implements the SortedMap interface.

Learning Objectives

Explain the purpose of TreeMap in a practical learning context.
Identify the main ideas, terms, and decisions involved in TreeMap.
Apply TreeMap in a simple real-world scenario or practice task.

Introduction

TreeMap is a part of Java's Collection Framework that implements the SortedMap interface.

It stores key-value pairs in a sorted order based on the natural ordering of keys or a custom comparator.

This tutorial will guide you through the basics of TreeMap, its features, and how to use it effectively.

A map that keeps its entries sorted by keys.

What is TreeMap?

TreeMap is a Red-Black tree-based implementation of the NavigableMap interface.

It maintains ascending order of keys, which makes it useful when you need sorted data.

Unlike HashMap, TreeMap guarantees log(n) time cost for the basic operations like get, put, and remove.

Implements NavigableMap and SortedMap interfaces.
Stores entries in sorted order by keys.
Allows null values but does not allow null keys.
Operations have O(log n) time complexity.

Creating and Using a TreeMap

You can create a TreeMap by simply instantiating it with the default constructor.

By default, it sorts keys according to their natural ordering.

Alternatively, you can provide a custom Comparator to define your own sorting logic.

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

Basic Operations

You can add, retrieve, and remove entries using put, get, and remove methods.

TreeMap also provides methods like firstKey(), lastKey(), and subMap() to navigate the sorted map.

put(key, value) - adds or updates an entry.
get(key) - retrieves the value for a key.
remove(key) - deletes the entry for a key.
firstKey() - returns the lowest key.
lastKey() - returns the highest key.

When to Use TreeMap

TreeMap is ideal when you need to maintain a map in sorted order.

It is useful for range queries and when you want to iterate over keys in a sorted manner.

However, if you don't need sorting, HashMap offers faster performance.

Use TreeMap for sorted key access.
Use it when you need to perform range operations like subMap.
Avoid TreeMap if insertion order or unsorted access is sufficient.

Practical Example

This example creates a TreeMap of fruit names and their quantities. It prints the map and shows the first and last keys in sorted order.

This example demonstrates creating a TreeMap with keys sorted in reverse alphabetical order using a custom Comparator.

Examples

Basic TreeMap Example

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("Apple", 50);
        map.put("Banana", 20);
        map.put("Cherry", 30);

        System.out.println("TreeMap: " + map);
        System.out.println("First Key: " + map.firstKey());
        System.out.println("Last Key: " + map.lastKey());
    }
}

This example creates a TreeMap of fruit names and their quantities. It prints the map and shows the first and last keys in sorted order.

TreeMap with Custom Comparator

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

public class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>(Comparator.reverseOrder());
        map.put("Apple", 50);
        map.put("Banana", 20);
        map.put("Cherry", 30);

        System.out.println("TreeMap with reverse order: " + map);
    }
}

This example demonstrates creating a TreeMap with keys sorted in reverse alphabetical order using a custom Comparator.

Best Practices

Use TreeMap when you need sorted keys and efficient range queries.
Avoid using null keys as TreeMap does not support them.
Prefer natural ordering for keys unless a specific order is required.
Use subMap, headMap, and tailMap methods for efficient range operations.

Common Mistakes

Trying to insert null keys into TreeMap causing NullPointerException.
Using TreeMap when sorting is not required, leading to unnecessary overhead.
Assuming TreeMap maintains insertion order (it maintains sorted order instead).
Not providing a Comparator when keys are not naturally comparable.

Hands-on Exercise

Implement a TreeMap with Custom Sorting

Create a TreeMap that stores employee names as keys and their IDs as values, sorted by the length of the employee names.

Expected output: A TreeMap sorted by employee name length.

Hint: Use a Comparator that compares strings by their length.

Use TreeMap Range Queries

Create a TreeMap of integer keys and string values, then retrieve a subMap for keys between 10 and 30.

Expected output: A subMap containing entries with keys in the specified range.

Hint: Use the subMap method with inclusive or exclusive bounds.

Interview Questions

What is the difference between TreeMap and HashMap in Java?

Interview

TreeMap stores keys in sorted order and guarantees O(log n) time for basic operations, while HashMap stores keys in no particular order and offers average O(1) time for basic operations.

Can TreeMap have null keys?

Interview

No, TreeMap does not allow null keys because it uses the compareTo or Comparator methods which cannot handle null.

How does TreeMap maintain its order?

Interview

TreeMap uses a Red-Black tree data structure to maintain keys in sorted order.