TreeMap and Sorted Maps

Learning outcome: Use TreeMap to maintain sorted keys, supply comparators, navigate neighboring keys, and select between hash-based and tree-based maps.

TreeMap<K,V> is a map implementation that keeps its keys sorted. It implements SortedMap and NavigableMap, so it can answer range and nearest-key questions in addition to normal map operations.

In simple terms: a HashMap is a pile of index cards: quick to search, but in no particular order. A TreeMap is the same cards kept permanently in a sorted tray. Filing costs a little more, but the tray can always be read in order and can answer "which card comes just before this one?"

Sorted Key Order

A tree map uses either:

1. The natural order defined by the key type, or
2. A Comparator supplied when the map is created.

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

public class SortedStudents {
    public static void main(String[] args) {
        Map<Integer, String> students = new TreeMap<>();
        students.put(103, "Kabir");
        students.put(101, "Aarav");
        students.put(102, "Diya");

        System.out.println(students);
    }
}

Output:

{101=Aarav, 102=Diya, 103=Kabir}

The insertion order was 103, 101, 102, but iteration follows ascending key order.

Tree-Based Performance

TreeMap is implemented with a balanced red-black tree.

The trade-off is clear: HashMap usually provides faster direct lookup, while TreeMap pays for maintaining sorted order and navigation.

What O(log n) means here: every comparison discards half of the remaining keys, so a map of one million entries is searched in roughly twenty steps. That is slower than a single hash lookup, yet still very fast, and the cost is guaranteed rather than merely expected.

TreeMap Hierarchy

SortedMap adds ordered ranges. NavigableMap adds nearest-match operations such as lower, floor, ceiling, and higher.

Natural Order and Comparator Order

String keys use lexicographic natural order by default.

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

A comparator can reverse the order.

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

public class ReverseOrderMap {
    public static void main(String[] args) {
        Map<String, Integer> marks = new TreeMap<>(Comparator.reverseOrder());
        marks.put("Aman", 81);
        marks.put("Meera", 94);
        marks.put("Diya", 88);

        System.out.println(marks);
    }
}

Output:

{Meera=94, Diya=88, Aman=81}

The ordering should be consistent with equals. If the comparator considers two different keys equal by returning 0, the map treats them as the same key.

In simple terms: inside a TreeMap, "the same key" means "compares to 0"; equals is never consulted. A case-insensitive comparator therefore turns "Aman" and "aman" into one single key, and the second put overwrites the first.

Navigating Neighboring Keys

Suppose a grading map stores the minimum score for each grade.

In simple terms: floor looks downwards and ceiling looks upwards. This is exactly how grade slabs, tax slabs, and bulk-price tiers work. The score 68 is not stored in the map at all, yet floorEntry(68) finds the 60 boundary and answers "B".

import java.util.NavigableMap;
import java.util.TreeMap;

public class GradeLookup {
    public static void main(String[] args) {
        NavigableMap<Integer, String> grades = new TreeMap<>();
        grades.put(0, "F");
        grades.put(40, "D");
        grades.put(50, "C");
        grades.put(60, "B");
        grades.put(75, "A");

        int score = 68;
        System.out.println("Grade: " + grades.floorEntry(score).getValue());
        System.out.println("Next boundary: " + grades.higherKey(score));
    }
}

Output:

Grade: B
Next boundary: 75

Range Views

Tree maps can expose live views over a key range.

import java.util.NavigableMap;
import java.util.TreeMap;

public class RangeViewDemo {
    public static void main(String[] args) {
        NavigableMap<Integer, String> rooms = new TreeMap<>();
        rooms.put(101, "Lab A");
        rooms.put(102, "Lab B");
        rooms.put(201, "Lab C");
        rooms.put(202, "Lab D");

        System.out.println(rooms.headMap(200, false));
        System.out.println(rooms.tailMap(200, true));
        System.out.println(rooms.subMap(102, true, 202, false));
    }
}

Output:

{101=Lab A, 102=Lab B}
{201=Lab C, 202=Lab D}
{102=Lab B, 201=Lab C}

Because these are views, permitted changes can affect the original map.

Reading the boolean arguments: the true or false beside each boundary states whether that boundary key is included. So subMap(102, true, 202, false) means "from 102 inclusive up to 202 exclusive".

HashMap vs TreeMap

With natural ordering, keys must be mutually comparable. A null key cannot be compared and should not be used. Null values are permitted.

Common Mistakes

Practice

1. Store five product codes in a TreeMap and print them in ascending order.
2. Create a case-insensitive TreeMap<String, Integer> with a comparator.
3. Use floorEntry to find the pricing tier for a given quantity.
4. Print all entries between two roll numbers with subMap.

Quick Check

Lecture Quiz

Summary

TreeMap maintains keys in natural or comparator order and supports navigation and range views through NavigableMap. Its core operations are O(log n). Choose it when order is a requirement; choose HashMap for general-purpose hash lookup without ordering guarantees.