TreeMap

Java TreeMap is a Red-Black tree based implementation of Java’s Map interface.

The entries in a TreeMap are always sorted based on the natural ordering of the keys, or based on a custom Comparator that you can provide at the time of creation of the TreeMap.

The TreeMap class is part of Java’s collection framework. It implements the NavigableMap interface, which in turn extends the SortedMap interface. Following is the class hierarchy of TreeMap -

The SortedMap interface provides functionalities to maintain the ordering of keys. And the NavigableMap interface provides functionalities to navigate through the map. For example, finding the entry just greater than or just less than the given key, finding the first and last entry in the TreeMap etc.

Since a TreeMap implements NavigableMap interface, it has the functionalities of both the NavigableMap as well as the SortedMap.

Following are few key points to note about TreeMap in Java -

• A TreeMap is always sorted based on keys. The sorting order follows the natural ordering of keys. You may also provide a custom Comparator to the TreeMap at the time of creation to let it sort the keys using the supplied Comparator.

• A TreeMap cannot contain duplicate keys.

• TreeMap cannot contain the null key. However, It can have null values.

• TreeMap is not synchronized. Access to TreeMaps must be synchronized explicitly in a multi-threaded environment.

Creating a TreeMap

1. Simple TreeMap

This example shows how to create a simple TreeMap and add new key-value pairs to it. The entries in the TreeMap will be sorted based on the natural ordering of keys -

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

public class CreateTreeMapExample {
    public static void main(String[] args) {
        // Creating a TreeMap
        SortedMap<String, String> fileExtensions  = new TreeMap<>();

        // Adding new key-value pairs to a TreeMap
        fileExtensions.put("python", ".py");
        fileExtensions.put("c++", ".cpp");
        fileExtensions.put("kotlin", ".kt");
        fileExtensions.put("golang", ".go");
        fileExtensions.put("java", ".java");

        // Printing the TreeMap (Output will be sorted based on keys)
        System.out.println(fileExtensions);
    }

}

# Output
{c++=.cpp, golang=.go, java=.java, kotlin=.kt, python=.py}

2. TreeMap with a custom Comparator (Descending Order)

This example demonstrates how to create a TreeMap with a custom comparator that orders the TreeMap entries in the descending order of keys -

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

public class CreateTreeMapCustomComparatorExample {
    public static void main(String[] args) {
        // Creating a TreeMap with a Custom comparator (Descending order)
        SortedMap<String, String> fileExtensions = new TreeMap<>(new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s2.compareTo(s1);
            }
        });

        /*
            The above TreeMap with custom Comparator can be simply written as -
            SortedMap<String, String> fileExtensions = new TreeMap<>(Comparator.reverseOrder());
        */

        // Adding new key-value pairs to a TreeMap
        fileExtensions.put("python", ".py");
        fileExtensions.put("c++", ".cpp");
        fileExtensions.put("kotlin", ".kt");
        fileExtensions.put("golang", ".go");
        fileExtensions.put("java", ".java");

        // Printing the TreeMap (The keys will be sorted based on the supplied comparator)
        System.out.println(fileExtensions);

    }
}

# Output
{python=.py, kotlin=.kt, java=.java, golang=.go, c++=.cpp}

3. TreeMap with a custom Comparator (Case Insensitive Order)

The following example shows how to create a Case Insensitive Map by passing a custom CASE_INSENSITIVE_ORDER comparator to the TreeMap. The TreeMap will ignore case while ordering the keys.

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

public class CreateTreeMapCaseInsensitiveOrderExample {
    public static void main(String[] args) {
        // TreeMap with keys sorted by ignoring case
        SortedMap<String, String> fileExtensions = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);

        /*
            The above statement is the short form of -
            SortedMap<String, String> fileExtensions = new TreeMap<>(new Comparator<String>() {
                @Override
                public int compare(String s1, String s2) {
                    return s1.compareToIgnoreCase(s2);
                }
            });
        */

        fileExtensions.put("PYTHON", ".py");
        fileExtensions.put("c++", ".cpp");
        fileExtensions.put("KOTLIN", ".kt");
        fileExtensions.put("Golang", ".go");

        // The keys will be sorted ignoring the case (Try removing String.CASE_INSENSITIVE_ORDER and see the output)
        System.out.println(fileExtensions);
    }
}

# Output
{c++=.cpp, Golang=.go, KOTLIN=.kt, PYTHON=.py}

Accessing the entries of a TreeMap

The following example demonstrates how to -

• Find the size of a TreeMap.

• Check if a given key exists in a TreeMap.

• Retrieve the first entry in the TreeMap.

• Retrieve the last entry in the TreeMap.

• Retrieve the entry whose key is just lower than the given key.

• Retrieve the entry whose key is just higher than the given key.

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

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

        employees.put(1003, "Rajeev");
        employees.put(1001, "James");
        employees.put(1002, "Sachin");
        employees.put(1004, "Chris");

        System.out.println("Employees map : " + employees);

        // Finding the size of a TreeMap
        System.out.println("Total number of employees : " + employees.size());

        // Check if a given key exists in a TreeMap
        Integer id = 1004;
        if(employees.containsKey(id)) {
            // Get the value associated with a given key in a TreeMap
            String name = employees.get(id);
            System.out.println("Employee with id " + id + " : " + name);
        } else {
            System.out.println("Employee does not exist with id : " + id);
        }

        // Find the first and last entry
        System.out.println("First entry in employees map : " + employees.firstEntry());
        System.out.println("Last entry in employees map : " + employees.lastEntry());

        // Find the entry whose key is just less than the given key
        Map.Entry<Integer, String> employeeJustBelow = employees.lowerEntry(1002);
        System.out.println("Employee just below id 1002 : " + employeeJustBelow);

        // Find the entry whose key is just higher than the given key
        Map.Entry<Integer, String> employeeJustAbove = employees.higherEntry(1002);
        System.out.println("Employee just above id 1002 : " + employeeJustAbove);
    }
}

# Output
Employees map : {1001=James, 1002=Sachin, 1003=Rajeev, 1004=Chris}
Total number of employees : 4
Employee with id 1004 : Chris
First entry in employees map : 1001=James
Last entry in employees map : 1004=Chris
Employee just below id 1002 : 1001=James
Employee just above id 1002 : 1003=Rajeev

Removing Entries from a TreeMap

The example below shows how to -

• Remove a key from a TreeMap.

• Remove a key from a TreeMap only if it is associated with a given value.

• Remove the first entry of the TreeMap.

• Remove the last entry of the TreeMap.

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

public class RemoveEntriesFromTreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, String> countryISOCodeMapping = new TreeMap<>();

        countryISOCodeMapping.put("India", "IN");
        countryISOCodeMapping.put("United States of America", "US");
        countryISOCodeMapping.put("China", "CN");
        countryISOCodeMapping.put("United Kingdom", "UK");
        countryISOCodeMapping.put("Russia", "RU");
        countryISOCodeMapping.put("Japan", "JP");

        System.out.println("CountryISOCodeMapping : " + countryISOCodeMapping);

        // Remove the mapping for a given key
        String countryName = "Japan";
        String isoCode = countryISOCodeMapping.remove(countryName);
        if(isoCode != null) {
            System.out.println("Removed (" + countryName + " => " + isoCode + ") from the TreeMap. New TreeMap " + countryISOCodeMapping);
        } else {
            System.out.println(countryName + " does not exist, or it is mapped to a null value");
        }

        // Remove the mapping for the given key only if it is mapped to the given value
        countryName = "India";
        boolean isRemoved = countryISOCodeMapping.remove(countryName, "IA");
        System.out.println("Was the mapping removed for " + countryName + "? : " + isRemoved);

        // Remove the first entry from the TreeMap
        Map.Entry<String, String> firstEntry = countryISOCodeMapping.pollFirstEntry();
        System.out.println("Removed firstEntry : " + firstEntry + ", New TreeMap : " + countryISOCodeMapping);

        // Remove the last entry from the TreeMap
        Map.Entry<String, String> lastEntry = countryISOCodeMapping.pollLastEntry();
        System.out.println("Removed lastEntry : " + lastEntry + ", New TreeMap : " + countryISOCodeMapping);
    }
}

# Output
CountryISOCodeMapping : {China=CN, India=IN, Japan=JP, Russia=RU, United Kingdom=UK, United States of America=US}
Removed (Japan => JP) from the TreeMap. New TreeMap {China=CN, India=IN, Russia=RU, United Kingdom=UK, United States of America=US}
Was the mapping removed for India? : false
Removed firstEntry : China=CN, New TreeMap : {India=IN, Russia=RU, United Kingdom=UK, United States of America=US}
Removed lastEntry : United States of America=US, New TreeMap : {India=IN, Russia=RU, United Kingdom=UK}

Problems:

1. Write a Java program to associate the specified value with the specified key in a Tree Map. Go to the editor Click me to see the solution

2. Write a Java program to copy a Tree Map content to another Tree Map. Go to the editor Click me to see the solution

3. Write a Java program to search a key in a Tree Map. Go to the editor Click me to see the solution

4. Write a Java program to search a value in a Tree Map. Go to the editor Click me to see the solution

5. Write a Java program to get all keys from the given a Tree Map. Go to the editor Click me to see the solution

6. Write a Java program to delete all elements from a given Tree Map. Go to the editor Click me to see the solution

7. Write a Java program to sort keys in Tree Map by using comparator. Go to the editor Click me to see the solution

8. Write a Java program to get a key-value mapping associated with the greatest key and the least key in a map. Go to the editor Click me to see the solution

9. Write a Java program to get the first (lowest) key and the last (highest) key currently in a map. Go to the editor Click me to see the solution

10. Write a Java program to get a reverse order view of the keys contained in a given map. Go to the editor Click me to see the solution

11. Write a Java program to get a key-value mapping associated with the greatest key less than or equal to the given key. Go to the editor Click me to see the solution

12. Write a Java program to get the greatest key less than or equal to the given key. Go to the editor Click me to see the solution

13. Write a Java program to get the portion of a map whose keys are strictly less than a given key. Go to the editor Click me to see the solution

14. Write a Java program to get the portion of this map whose keys are less than (or equal to, if inclusive is true) a given key. Go to the editor Click me to see the solution

15. Write a Java program to get the least key strictly greater than the given key. Return null if there is no such key. Go to the editor Click me to see the solution

16. Write a Java program to get a key-value mapping associated with the greatest key strictly less than the given key. Return null if there is no such key. Go to the editor Click me to see the solution

17. Write a Java program to get the greatest key strictly less than the given key. Return null if there is no such key. Go to the editor Click me to see the solution

18. Write a Java program to get NavigableSet view of the keys contained in a map. Go to the editor Click me to see the solution

19. Write a Java program to remove and get a key-value mapping associated with the least key in a map. Go to the editor Click me to see the solution

20. Write a Java program to remove and get a key-value mapping associated with the greatest key in this map. Go to the editor Click me to see the solution

21. Write a Java program to get the portion of a map whose keys range from a given key (inclusive), to another key (exclusive). Go to the editor Click me to see the solution

22. Write a Java program to get the portion of a map whose keys range from a given key to another key. Go to the editor Click me to see the solution

23. Write a Java program to get a portion of a map whose keys are greater than or equal to a given key. Go to the editor Click me to see the solution

24. Write a Java program to get a portion of a map whose keys are greater than to a given key. Go to the editor Click me to see the solution

25. Write a Java program to get a key-value mapping associated with the least key greater than or equal to the given key. Return null if there is no such key. Go to the editor Click me to see the solution

26. Write a Java program to get the least key greater than or equal to the given key. Returns null if there is no such key. Go to the editor Click me to see the solution