Understanding TreeMap and Sorted Maps in Java

Course: Core Java Training

Topic: Understanding TreeMap and Sorted Maps

Course Link: Core Java Training Course

Demo Link: Register for a Course Demo

Website: JustAcademy

1. Introduction to TreeMap and Sorted Maps

Java provides several data structures for storing and organizing key-value pairs. The Map interface allows each key to be associated with a value, while the SortedMap interface adds the ability to maintain mappings in sorted key order.

TreeMap is a commonly used implementation of the SortedMap interface. It automatically arranges its keys according to their natural ordering or according to a custom Comparator.

For example, if employee IDs are inserted in the order 103, 101, and 102, a TreeMap with integer keys will iterate through them in ascending order: 101, 102, and 103.

Learning Objectives

• Understand the purpose of the TreeMap class.
• Learn about the SortedMap interface.
• Create and manipulate TreeMap objects.
• Understand natural ordering and custom comparators.
• Use methods such as firstKey(), lastKey(), headMap(), tailMap(), and subMap().
• Compare TreeMap with HashMap and LinkedHashMap.
• Apply sorted maps to practical Java programming problems.

2. What Is TreeMap in Java?

TreeMap is a class in the java.util package that implements the NavigableMap interface, which extends SortedMap. It stores key-value pairs in sorted key order.

Internally, TreeMap uses a self-balancing Red-Black tree. This data structure helps it maintain sorted keys while supporting efficient searching, insertion, and deletion.

Key Characteristics of TreeMap

• Stores data as key-value pairs.
• Does not allow duplicate keys.
• Allows duplicate values.
• Maintains keys in ascending order by default.
• Supports custom sorting through a Comparator.
• Generally provides O(log n) time for get(), put(), remove(), and containsKey().
• Does not permit null keys under natural ordering; null values are permitted.
• Is not synchronized for concurrent modification by multiple threads.

Basic Syntax

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

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

In this declaration, integer keys are sorted in ascending order, and each key maps to a string value.

3. Understanding the SortedMap Interface

SortedMap is an interface in Java's Collections Framework that extends Map. It defines behavior for maps whose keys are maintained in a sorted order.

The interface specifies methods for obtaining the first and last keys, retrieving ranges of mappings, and checking the comparator used for ordering.

Important Features of SortedMap

• Keys are maintained according to a consistent ordering.
• Keys must be mutually comparable using natural ordering or a supplied comparator.
• Supports range views through headMap(), tailMap(), and subMap().
• Provides firstKey() and lastKey() for accessing the lowest and highest keys.
• Does not permit duplicate keys.
• Can be implemented by classes such as TreeMap.

SortedMap Syntax

import java.util.SortedMap;
import java.util.TreeMap;

SortedMap<Integer, String> employees = new TreeMap<>();

Declaring a variable using the SortedMap interface allows the program to depend on the interface rather than on the specific implementation.

4. Difference Between Map, SortedMap, and TreeMap

5. Creating a TreeMap

To create a TreeMap, import the required classes from java.util and instantiate the TreeMap class.

Example 1: Basic TreeMap

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

public class TreeMapExample {
    public static void main(String[] args) {
        Map<Integer, String> students = new TreeMap<>();

        students.put(103, "Rahul");
        students.put(101, "Priya");
        students.put(102, "Aarav");

        System.out.println(students);
    }
}

Output:

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

Explanation: The keys were inserted in the order 103, 101, and 102. TreeMap automatically arranges them in ascending order when the map is displayed or iterated over.

6. Adding and Updating Entries

The put() method adds a key-value mapping to a TreeMap. If the specified key already exists according to the map's ordering, the associated value is replaced.

import java.util.TreeMap;

public class AddUpdateExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> products = new TreeMap<>();

        products.put(30, "Monitor");
        products.put(10, "Laptop");
        products.put(20, "Keyboard");

        products.put(20, "Mechanical Keyboard");

        System.out.println(products);
    }
}

Output:

{10=Laptop, 20=Mechanical Keyboard, 30=Monitor}

The mapping for key 20 is updated rather than creating a second entry with the same key.

7. Retrieving and Removing Entries

7.1 get()

The get() method retrieves a value associated with a specified key.

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

cities.put(1, "Mumbai");
cities.put(2, "Pune");

System.out.println(cities.get(1));

Output:

Mumbai

7.2 remove()

The remove() method removes the mapping associated with a key.

cities.remove(2);
System.out.println(cities);

Output:

{1=Mumbai}

7.3 containsKey() and containsValue()

These methods check whether a specified key or value is present.

System.out.println(cities.containsKey(1));
System.out.println(cities.containsValue("Mumbai"));

Output:

true
true

8. Understanding Natural Ordering

When a TreeMap is created without a Comparator, it uses the natural ordering of its keys. The key type must implement Comparable, and the keys must be mutually comparable.

Examples of natural ordering include:

• Integer keys: ascending numeric order.
• String keys: lexicographical order based on Java's string comparison rules.
• Date keys: chronological order when the key type supports natural ordering.

Example: Sorting String Keys

import java.util.TreeMap;

public class StringKeySorting {
    public static void main(String[] args) {
        TreeMap<String, Integer> scores = new TreeMap<>();

        scores.put("Zara", 85);
        scores.put("Amit", 92);
        scores.put("Neha", 88);

        System.out.println(scores);
    }
}

Output:

{Amit=92, Neha=88, Zara=85}

String keys are sorted according to their natural lexicographical comparison, which is case-sensitive. This is not necessarily the same as locale-aware alphabetical sorting.

9. Sorting with a Custom Comparator

A Comparator defines a custom ordering for keys. It is useful when the default natural ordering does not match the application's requirements.

Example: Descending Numeric Order

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

public class DescendingTreeMap {
    public static void main(String[] args) {
        TreeMap<Integer, String> students =
            new TreeMap<>(Comparator.reverseOrder());

        students.put(101, "Aarav");
        students.put(103, "Rahul");
        students.put(102, "Priya");

        System.out.println(students);
    }
}

Output:

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

Example: Sorting Strings by Length

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

public class StringLengthSorting {
    public static void main(String[] args) {
        Comparator<String> byLength =
            Comparator.comparingInt(String::length)
                      .thenComparing(Comparator.naturalOrder());

        TreeMap<String, Integer> words = new TreeMap<>(byLength);

        words.put("Java", 1);
        words.put("SQL", 2);
        words.put("Python", 3);
        words.put("Go", 4);

        System.out.println(words);
    }
}

Output:

{Go=4, SQL=2, Java=1, Python=3}

The comparator sorts keys by length first and then by natural string order. Including a secondary comparison is important when distinct keys must remain distinct in the sorted map.

10. Important TreeMap and SortedMap Methods

11. Using firstKey() and lastKey()

The firstKey() and lastKey() methods retrieve the smallest and largest keys according to the map's ordering.

import java.util.TreeMap;

public class FirstLastKeyExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> employees = new TreeMap<>();

        employees.put(105, "Ravi");
        employees.put(101, "Neha");
        employees.put(103, "Amit");

        System.out.println("First key: " + employees.firstKey());
        System.out.println("Last key: " + employees.lastKey());
    }
}

Output:

First key: 101
Last key: 105

These methods are useful for retrieving boundary keys in sorted datasets. Check that the map is not empty before calling them.

12. Working with headMap(), tailMap(), and subMap()

SortedMap supports range views, allowing you to work with a portion of the mappings without manually filtering every entry.

12.1 headMap()

headMap(toKey) returns a view of mappings whose keys are strictly less than the specified key.

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.headMap(30));

Output:

{10=A, 20=B}

12.2 tailMap()

tailMap(fromKey) returns a view of mappings whose keys are greater than or equal to the specified key.

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

Output:

{30=C, 40=D}

12.3 subMap()

subMap(fromKey, toKey) returns a view whose keys start at the inclusive lower boundary and end before the exclusive upper boundary.

System.out.println(map.subMap(20, 40));

Output:

{20=B, 30=C}

Important: These methods return backed views, not independent copies. Changes made through a view can affect the original map, and changes to the original map may be reflected in the view. Inserting a key outside a range-restricted view causes an IllegalArgumentException.

13. NavigableMap and Additional Navigation Methods

TreeMap implements NavigableMap, which extends SortedMap and adds methods for locating keys near a given key, retrieving entries, and navigating in reverse order.

Example: Finding Nearby Keys

import java.util.TreeMap;

public class NavigationExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> scores = new TreeMap<>();

        scores.put(10, "Low");
        scores.put(20, "Medium");
        scores.put(30, "High");
        scores.put(40, "Very High");

        System.out.println(scores.lowerKey(30));
        System.out.println(scores.floorKey(30));
        System.out.println(scores.ceilingKey(25));
        System.out.println(scores.higherKey(30));
    }
}

Output:

20
30
30
40

14. Iterating Through a TreeMap

TreeMap provides several ways to iterate through keys, values, and complete entries. The iteration order follows the map's configured key ordering.

14.1 Using entrySet()

for (var entry : map.entrySet()) {
    System.out.println(
        entry.getKey() + " = " + entry.getValue()
    );
}

The var keyword is supported from Java 10 for local variable type inference. For earlier Java versions, use Map.Entry<Integer, String> or the appropriate key and value types.

14.2 Using keySet()

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

14.3 Using forEach()

map.forEach((key, value) ->
    System.out.println(key + " -> " + value)
);

Use entrySet() when both keys and values are needed, as it makes the mapping relationship explicit.

15. TreeMap vs HashMap vs LinkedHashMap

Choose TreeMap when sorted order or range operations are requirements. If ordering is unnecessary and lookup performance is the priority, HashMap is often a suitable choice. If insertion order matters, consider LinkedHashMap.

16. Performance and Internal Working of TreeMap

TreeMap uses a Red-Black tree, a self-balancing binary search tree. Each node stores a key, a value, links to other nodes, and balancing information.

How It Works

1. The map compares the new key with keys already in the tree.
2. The comparison determines whether the search continues to the left or right.
3. The new mapping is inserted at the appropriate position.
4. The tree may rebalance itself to maintain efficient operations.
5. When iterated, the entries are visited in sorted key order.

Time Complexity

Here, n is the number of mappings. These bounds make TreeMap useful when ordered operations are important, although hash-based maps may be faster for common lookups when sorting is not needed.

17. Using Custom Objects as TreeMap Keys

TreeMap can use custom objects as keys, but it must be able to compare them. You can implement Comparable on the key class or provide a Comparator when creating the map.

Example: Employee IDs and Names

import java.util.TreeMap;

class Employee implements Comparable<Employee> {
    private final int id;
    private final String name;

    Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    @Override
    public int compareTo(Employee other) {
        return Integer.compare(this.id, other.id);
    }

    @Override
    public String toString() {
        return id + " - " + name;
    }
}

public class EmployeeTreeMapExample {
    public static void main(String[] args) {
        TreeMap<Employee, String> employees = new TreeMap<>();

        employees.put(new Employee(103, "Rahul"), "Developer");
        employees.put(new Employee(101, "Priya"), "Tester");
        employees.put(new Employee(102, "Aarav"), "Analyst");

        employees.forEach((employee, role) ->
            System.out.println(employee + " : " + role)
        );
    }
}

Explanation: The compareTo() method sorts Employee keys by ID. The comparison determines key identity for the purposes of TreeMap: if two Employee objects compare as zero, TreeMap treats them as the same key even if they are different objects.

Make sure the comparator's ordering is consistent with equals() whenever possible. An inconsistent ordering can cause a sorted map to behave differently from what users expect from the general Map contract.

18. Common Errors and Troubleshooting

19. Best Practices for TreeMap and SortedMap

• Use TreeMap when sorted keys or range-based operations are required.
• Declare variables with the SortedMap or NavigableMap interface when the program needs only the interface's behavior.
• Use a Comparator to express custom ordering clearly.
• Ensure all keys are mutually comparable.
• Keep comparison logic stable while keys are stored in the map.
• Make the comparator consistent with equals whenever practical.
• Check whether the map is empty before calling firstKey() or lastKey().
• Remember that headMap(), tailMap(), and subMap() return backed views.
• Do not assume TreeMap is thread-safe.
• Use a hash-based Map if sorted order and range operations are not required and hashing better fits the use case.

20. Practical Example: Product Inventory Sorted by Product ID

This example demonstrates how TreeMap can organize inventory records by product ID so that products can be displayed in ascending ID order.

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

public class ProductInventory {
    public static void main(String[] args) {
        TreeMap<Integer, String> inventory = new TreeMap<>();

        inventory.put(5003, "Keyboard");
        inventory.put(5001, "Laptop");
        inventory.put(5002, "Mouse");
        inventory.put(5004, "Monitor");

        System.out.println("Inventory sorted by product ID:");

        for (Map.Entry<Integer, String> item : inventory.entrySet()) {
            System.out.println(
                "Product ID: " + item.getKey() +
                ", Product: " + item.getValue()
            );
        }

        System.out.println("First product ID: " + inventory.firstKey());
        System.out.println("Last product ID: " + inventory.lastKey());
    }
}

Expected output:

Inventory sorted by product ID:
Product ID: 5001, Product: Laptop
Product ID: 5002, Product: Mouse
Product ID: 5003, Product: Keyboard
Product ID: 5004, Product: Monitor
First product ID: 5001
Last product ID: 5004

This pattern is useful for inventory listings, ordered identifiers, and reports that need consistent ascending key order.

21. Hands-On Exercises

Exercise 1: Student Records

Create a TreeMap where student roll numbers are keys and student names are values. Insert five students in random order and display them in ascending roll-number order.

Exercise 2: Reverse Sorting

Create a TreeMap using Comparator.reverseOrder() and verify that integer keys are displayed in descending order.

Exercise 3: Price Range

Store product IDs and prices in a TreeMap. Use subMap() to display mappings between two specified IDs.

Exercise 4: Find Nearby Keys

Use lowerKey(), floorKey(), ceilingKey(), and higherKey() to find keys around a target number.

Exercise 5: Custom Object Sorting

Create an Employee class that implements Comparable and use employee objects as TreeMap keys. Sort them by employee ID.

22. Interview Questions and Answers

Q1. What is TreeMap in Java?

TreeMap is a Map implementation that stores mappings in sorted key order using natural ordering or a supplied Comparator.

Q2. What is SortedMap?

SortedMap is an interface extending Map. It defines operations for sorted key order, first and last keys, and key-range views.

Q3. How does TreeMap maintain sorted order?

It uses a self-balancing Red-Black tree and compares keys to maintain their order.

Q4. What is the difference between TreeMap and HashMap?

TreeMap sorts keys and generally performs key operations in O(log n) time. HashMap does not guarantee iteration order and generally provides expected O(1) lookup and insertion.

Q5. Can TreeMap contain duplicate keys?

No. A key can have only one current mapping according to the TreeMap's comparison rules.

Q6. Can TreeMap contain null keys?

TreeMap using natural ordering does not permit null keys. A custom comparator may permit null, but this depends on the comparator's implementation.

Q7. What is the purpose of Comparator?

A Comparator defines custom ordering for keys, such as descending numbers or sorting strings by length.

Q8. What is the difference between headMap() and tailMap()?

headMap() returns a range of keys below an upper boundary. tailMap() returns a range beginning at an inclusive lower boundary.

Q9. What is subMap() used for?

It returns a backed view of entries within a specified key range. The SortedMap overload includes the lower boundary and excludes the upper boundary.

Q10. Is TreeMap thread-safe?

No. It requires suitable synchronization or another concurrency strategy if multiple threads access and modify it concurrently.

23. Quick Revision Checklist

• TreeMap implements NavigableMap and SortedMap.
• SortedMap extends the Map interface.
• TreeMap sorts keys in ascending order by default.
• A Comparator can define custom ordering.
• Keys must be mutually comparable.
• Duplicate keys are not allowed.
• TreeMap uses a Red-Black tree.
• Basic lookup, insertion, and removal operations generally take O(log n) time.
• firstKey() and lastKey() return the boundary keys.
• headMap(), tailMap(), and subMap() return range views.
• NavigableMap adds lower, floor, ceiling, and higher navigation methods.
• TreeMap is not synchronized by default.

24. Conclusion

TreeMap and SortedMap are important components of Java's Collections Framework for working with ordered key-value data. The SortedMap interface defines the operations available for sorted maps, while TreeMap provides a practical implementation backed by a self-balancing Red-Black tree.

By learning natural ordering, custom comparators, range views, and navigation methods, you can build programs that efficiently organize and search sorted data. Practice the examples and exercises to strengthen your understanding of TreeMap and other Core Java collection types.

Continue Learning: Explore the Core Java Training course, register for a course demo, or visit the JustAcademy website.