TreeMap in Java Explained (with Examples)

Dec 05, 2023
9 Minutes Read

Why Trust Us
We uphold a strict editorial policy that emphasizes factual accuracy, relevance, and impartiality. Our content is crafted by top technical writers with deep knowledge in the fields of computer science and data science, ensuring each piece is meticulously reviewed by a team of seasoned editors to guarantee compliance with the highest standards in educational content creation and publishing.
By Nihal Mahansaria

TreeMap in Java Explained (with Examples)

The TreeMap is a powerful and flexible data structure that stands out in the large field of Java Collections. Unlike the others, TeeMap keeps its elements arranged logically, offering a seamless method of organizing and navigating through data. Here is your guide to TreeMap in Java, along with its various use cases.

What is TreeMap in Java?

At its core, a TreeMap is a Red-Black Tree based implementation of the NavigableMap interface.

TreeMap ensures the elements are stored in a sorted order based on their natural ordering or a custom comparator. This sorted nature enables efficient retrieval and range-based operations.

ordering of treemap

The defining features of TreeMap include its ability to maintain unique keys and adhere to the NavigableMap interface. The latter endows TreeMap with advanced navigation methods, making it a powerful tool for various scenarios.

Comparing TreeMap with other maps like HashMap and LinkedHashMap is crucial for choosing the right data structure for a given task.

While HashMap offers constant-time performance for basic operations, TreeMap sorted nature makes it suitable for scenarios where order matters. LinkedHashMap, on the other hand, maintains the insertion order, striking a balance between unordered HashMap and sort TreeMap.

Let's delve into a simple example to illustrate the basic characteristics of TreeMap:

import java.util.*;

public class TreeMapExample {

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

        officeRooms.put(101, "Human Resources");
        officeRooms.put(102, "Marketing");
        officeRooms.put(103, "Finance");
        officeRooms.put(104, "Engineering");

        System.out.println("Office Rooms Allocation:");
        for (Map.Entry<Integer, String> entry : officeRooms.entrySet()) {
            System.out.println("Room " + entry.getKey() + ": " + entry.getValue());
        }
    }

}

In this example, we create a TreeMap of integers mapped to strings. The elements are inserted in an arbitrary order, but the TreeMap automatically sorts them based on their keys.

Output:

Office Rooms Allocation:
Room 101: Human Resources
Room 102: Marketing
Room 103: Finance
Room 104: Engineering

Let’s understand how to implement TreeMap.

The TreeMap is implemented as a Red-Black Tree, a self-balancing binary search tree. This structure ensures that the trère remains relatively balanced, preventing performance degradation. The Red-Black Tree's characteristics guarantee logarithmic time complexity for common operations like insertion, deletion, and search.

The Time complexity for Insertion, Deletion, and Search is O(log N), where N is the number of elements in the TreeMap. The space complexity is O(N) for storing N elements.

Let's illustrate these complexities with a practical example:

import java.util.*;

public class TreeMapComplexityExample {

    public static void main(String[] args) {
        TreeMap<String, Double> productPrices = new TreeMap<>();

        productPrices.put("Laptop", 1200.00);
        productPrices.put("Smartphone", 800.00);
        productPrices.put("Tablet", 500.00);
        productPrices.put("Headphones", 100.00);

        productPrices.remove("Tablet");

        System.out.println("Product Price for 'Smartphone': $" + productPrices.get("Smartphone"));
    }

}

Here, we insert elements, delete one, and then search for another. The logarithmic time complexity of these operations is evident in TreeMap's efficient performance.

Output:

Product Price for 'Smartphone': $800.0

Various TreeMap Operations

Following are some TreeMap Operations.

Insertion and Deletion

TreeMap provides efficient methods for adding and removing elements.

The put(key, value) method inserts a key-value pair into the Tree Map. The TreeMap automatically maintains the sorted order. To remove an element, use the remove(key) method. The Red-Black Tree structure ensures the tree remains balanced after deletion.

Let's demonstrate these operations:

import java.util.*;

public class TreeMapOperationsExample {

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

        examScores.put("Alice", 85);
        examScores.put("Bob", 92);
        examScores.put("Charlie", 78);
        examScores.put("Diana", 95);

        System.out.println("After Insertion: " + examScores);

        examScores.remove("Charlie");

        System.out.println("After Deletion: " + examScores);
    }

}

Output:

After Insertion: {Alice=85, Bob=92, Charlie=78, Diana=95}
After Deletion: {Alice=85, Bob=92, Diana=95}

Here, we insert elements into the TreeMap and then remove the element with key 2. The TreeMap adjusts itself to maintain its sorted order.

Searching and Retrieving

TreeMap provides efficient methods for searching and retrieving elements.

The get(key) method retrieves the value associated with the specified key. Methods like firstKey(), lastKey(), ceilingKey(), and floorKey() provide ways to navigate through the TreeMap.

Let's see an example:

import java.util.*;

public class TreeMapSearchExample {

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

        productCodes.put("P001", 150);
        productCodes.put("P002", 220);
        productCodes.put("P003", 180);
        productCodes.put("P004", 300);

        System.out.println("Value for key 'P002': " + productCodes.get("P002"));

        System.out.println("First key: " + productCodes.firstKey());
        System.out.println("Last key: " + productCodes.lastKey());
        System.out.println("Ceiling key for 'P002': " + productCodes.ceilingKey("P002"));
        System.out.println("Floor key for 'P002': " + productCodes.floorKey("P002"));
    }

}

Output:

Value for key 'P002': 220
First key: P001
Last key: P004
Ceiling key for 'P002': P002
Floor key for 'P002': P001

Iterations in TreeMap

Let’s learn how we can iterate in TreeMap.

1) Iterating through Keys, Values, and Entries

TreeMap provides multiple ways to iterate through its elements: by keys, values, or entries.

KeySet: The keySet() method returns a set of all keys in the TreeMap.

Values: The values() method returns a collection of all values in the TreeMap.

EntrySet: The entrySet() method returns a set of key-value pairs (entries) in the TreeMap.

Let's explore these iteration methods:

import java.util.*;

public class TreeMapIterationExample {

    public static void main(String[] args) {
        TreeMap<String, Double> employeeSalaries = new TreeMap<>();

        employeeSalaries.put("John", 55000.00);
        employeeSalaries.put("Alice", 62000.00);
        employeeSalaries.put("Ethan", 58000.00);
        employeeSalaries.put("Sophia", 60000.00);

        System.out.println("Keys: " + employeeSalaries.keySet());
        System.out.println("Values: " + employeeSalaries.values());

        for (Map.Entry<String, Double> entry : employeeSalaries.entrySet()) {
            System.out.println("Employee: " + entry.getKey() + ", Salary: $" + entry.getValue());
        }
    }

}

Output:

Keys: [Alice, Ethan, John, Sophia]
Values: [62000.0, 58000.0, 55000.0, 60000.0]
Employee: Alice, Salary: $62000.0
Employee: Ethan, Salary: $58000.0
Employee: John, Salary: $55000.0
Employee: Sophia, Salary: $60000.0

In this example, we showcase how to iterate through keys, values, and entries in a TreeMap.

2) Custom Ordering

TreeMap allows you to define a custom comparator for sorting elements. This is particularly useful when dealing with complex objects or custom sorting criteria.

Take an example:

import java.util.*;

public class TreeMapCustomOrderExample {

    public static void main(String[] args) {
        Comparator<Integer> customComparator = Collections.reverseOrder();
        TreeMap<Integer, String> customOrderedMap = new TreeMap<>(customComparator);

        customOrderedMap.put(1001, "Project A");
        customOrderedMap.put(750, "Client X");
        customOrderedMap.put(1200, "Product Launch");
        customOrderedMap.put(900, "Business Strategy");

        System.out.println("Custom Order: " + customOrderedMap);
    }

}

Output:

Custom Order: {1200=Product Launch, 1001=Project A, 900=Business Strategy, 750=Client X}

Here, we define a custom comparator to sort the Tree Map in descending order.

Use Cases of TreeMap

Following are some use cases and applications of TreeMap.

1) Sorting in TreeMap

One of the primary use cases of TreeMap is sorting. As TreeMap maintains elements in sorted order, it becomes a natural choice when sorting is a crucial aspect of data manipulation. This is especially beneficial when dealing with custom objects or scenarios where sorting by natural order is essential.

Let's consider an example where we sort a TreeMap of custom objects:

import java.util.*;

class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

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

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

public class TreeMapSortingExample {

    public static void main(String[] args) {
        TreeMap<Person, String> personMap = new TreeMap<>();

        personMap.put(new Person("Alice", 28), "Engineer");
        personMap.put(new Person("Bob", 35), "Doctor");
        personMap.put(new Person("Charlie", 22), "Artist");

        System.out.println("Sorted by Age: " + personMap);
    }

}

Output:

Sorted by Age: {Person{name='Charlie', age=22}=Artist, Person{name='Alice', age=28}=Engineer, Person{name='Bob', age=35}=Doctor}

In this example, the TreeMap is automatically sorted based on the edge of the Person objects.

2) Range Operations in TreeMap

TreeMap provides methods for performing range-based operations, such as subMap, headMap, and tailMap. These methods allow you to retrieve portions of the Tree Map based on specified key ranges.

Let's see an example:

import java.util.*;

public class TreeMapRangeOperationsExample {

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

        ageMap.put("Alice", 25);
        ageMap.put("Bob", 30);
        ageMap.put("Charlie", 22);
        ageMap.put("Diana", 27);

        SortedMap<String, Integer> subMap = ageMap.subMap("Bob", "Diana");
        SortedMap<String, Integer> headMap = ageMap.headMap("Charlie");
        SortedMap<String, Integer> tailMap = ageMap.tailMap("Bob");

        System.out.println("SubMap: " + subMap);
        System.out.println("HeadMap: " + headMap);
        System.out.println("TailMap: " + tailMap);
    }

}

Output:

SubMap: {Bob=30, Charlie=22}
HeadMap: {Alice=25, Bob=30}
TailMap: {Bob=30, Charlie=22, Diana=27}

Here, we demonstrate the use of subMap, headMap, and tailMap to extract specific ranges from the TreeMap.

Best Practices for Programmers

Follow these best practices for improved performance in TreeMap.

Efficient memory management is essential when working with large datasets. TreeMap, being a balanced tree structure, ensures logarithmic time complexity for operations but requires additional memory to maintain its structure.

Consider the following tips for memory management: After populating the TreeMap, calling trimToSize() can reduce its capacity to the minimum required to hold the elements.

import java.util.*;

public class TreeMapMemoryManagementExample {

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

        treeMap.put(3, "Widget");
        treeMap.put(1, "Clock");
        treeMap.put(2, "Navbar");
        treeMap.put(4, "Taskbar");

        ((TreeMap<Integer, String>) treeMap).trimToSize();
    }

}

Also, selecting the appropriate map implementation depends on the specific use case:

Use TreeMap when sorting or maintaining order is crucial.
Prefer HashMap for constant-time performance in scenarios where order is not important.
Consider LinkedHashMap when the insertion order needs to be preserved.

See an example:

import java.util.*;

public class ChooseRightMapExample {

    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        HashMap<Integer, String> hashMap = new HashMap<>();
        LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<>();
    }

}

In this example, we showcase the creation of TreeMap, HashMap, and LinkedHashMap based on specific requirements.

Common Pitfalls and How to Avoid Them

Some common pitfalls in TreeMap are:

1) Null Handling

TreeMap does not allow null keys but allows multiple null values. It's important to handle null values appropriately to avoid NullPointerException. When using custom comparators, ensure they handle null values gracefully.

import java.util.*;

public class TreeMapNullHandlingExample {

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

        treeMap.put(1, null);  // OK
        // treeMap.put(null, "Value"); // Uncommenting this line will result in NullPointerException
    }

}

2) Concurrent Modification

Modifying a TreeMap while iterating over it can lead to ConcurrentModificationException. To avoid this, use an explicit iterator or make modifications through the iterator.

import java.util.*;

public class TreeMapConcurrentModificationExample {

    public static void main(String[] args) {
        TreeMap<String, Double> productPrices = new TreeMap<>();

        productPrices.put("Laptop", 1200.00);
        productPrices.put("Smartphone", 800.00);
        productPrices.put("Headphones", 200.00);
        productPrices.put("Tablet", 500.00);

        // Incorrect way: Modifying during iteration
        for (Map.Entry<String, Double> entry : productPrices.entrySet()) {
            if (entry.getKey().equals("Headphones")) {
                productPrices.remove("Headphones"); // Throws ConcurrentModificationException
            }
        }
    }

}

To avoid the ConcurrentModificationException, you can use an explicit iterator:

// Correct way: Using an explicit iterator

Iterator<Map.Entry<String, Double>> iterator = productPrices.entrySet().iterator();

while (iterator.hasNext()) {

    Map.Entry<String, Double> entry = iterator.next();

    if (entry.getKey().equals("Headphones")) {

        // Correct: Modifying the TreeMap through the iterator

        iterator.remove();

    }

}

Conclusion

This brings an end to our blog on learning everything about Java TreeMap along with its various operations and use cases. If you have an assignment question on this concept, then you might want to get our top Java Homework Help online to solve it efficiently.

The Top 10 favtutor Features You Might Have Overlooked

TreeMap in Java Explained (with Examples)

What is TreeMap in Java?

Various TreeMap Operations

Insertion and Deletion

Searching and Retrieving

Iterations in TreeMap

1) Iterating through Keys, Values, and Entries

2) Custom Ordering

Use Cases of TreeMap

1) Sorting in TreeMap

2) Range Operations in TreeMap

Best Practices for Programmers

Common Pitfalls and How to Avoid Them

1) Null Handling

2) Concurrent Modification

Conclusion

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author

Nihal Mahansaria

More by FavTutor Blogs

The Top 10 favtutor Features You Might Have Overlooked

TreeMap in Java Explained (with Examples)

What is TreeMap in Java?

Various TreeMap Operations

Insertion and Deletion

Searching and Retrieving

Iterations in TreeMap

1) Iterating through Keys, Values, and Entries

2) Custom Ordering

Use Cases of TreeMap

1) Sorting in TreeMap

2) Range Operations in TreeMap

Best Practices for Programmers

Common Pitfalls and How to Avoid Them

1) Null Handling

2) Concurrent Modification

Conclusion

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author

Nihal Mahansaria

More by FavTutor Blogs

Reverse Level Order Traversal in Binary Tree (with code)

Vedanti Kshirsagar

Types of Inheritance in Python (with Examples)

Kusum Jain

What does xrange() do in Python?

Kusum Jain