Java TreeMap

In the last lesson you learned about Java LinkedHashMap, which stores key-value pairs in insertion order. Just like sets had a sorted version, maps do too. When you need your map’s keys kept in sorted order automatically, Java gives you the TreeMap, a HashMap’s ordered cousin.

🤔 Why a TreeMap?

Picture a real problem first. You are building a price list for a small shop. Customers ask things like “what is the cheapest item?” or “show me everything that costs between 100 and 500.” You also want to print the whole list from cheapest to most expensive every morning.

A HashMap makes this painful:

• It loops in an unpredictable order. No “cheapest,” no “in between.”
• For sorted output you must copy keys into a list and sort them yourself.
• For a range you must scan the whole map.

A TreeMap fixes all of that by keeping keys sorted at all times:

• A new key drops straight into its sorted position.
• Looping always visits keys in order, with no extra step.
• You can ask for the smallest, largest, or nearest key in one call.
• You can pull out a slice, like “all keys between 100 and 500,” cheaply.

Think of a HashMap as a pile of labelled boxes thrown into a room. You can grab any box instantly if you know its label, but the pile has no shape. A TreeMap is the same set of boxes lined up neatly on a shelf, smallest label on the left, largest on the right. Grabbing one box is a touch slower because you walk along the shelf. But now you can read them in order, and you can point at “everything from here to there.”

🧩 What is a TreeMap?

A TreeMap is a map that stores key-value pairs with its keys kept in sorted order. Everything you know about maps still applies. What’s new:

• Keys stay in natural sorted order: numbers ascending, Strings alphabetically.
• Keys are still unique. Put the same key twice and the new value overwrites the old one.
• It adds navigation methods to find the smallest, largest, or nearest keys, and to take slices.
• It does not allow a null key. Java cannot compare null against a real key to place it in order.

So if HashMap is the “fast map,” TreeMap is the “sorted map.” How it does this, in one breath:

• It is backed by a red-black tree, a self-balancing binary search tree.
• put and get are O(log n): time grows slowly as the map grows, because Java walks the tree.
• A HashMap’s put/get are O(1), so a TreeMap is a touch slower.
• For a few thousand entries the gap is tiny. You trade a little speed for sorted order and the navigation tools.

🔢 Keys must be comparable

A TreeMap can only sort keys it knows how to compare. This trips people up, so here it is plainly:

• Built-in types like Integer, Long, Double, and String already know how to compare themselves. They implement Comparable, so a TreeMap just works.
• Your own class does not know its order until you teach it.
• Teach it one of two ways: implement Comparable with a compareTo method, or pass a Comparator to the constructor.
• Skip both and the second put throws a ClassCastException. The TreeMap cannot place the key in order. We will see that mistake later.

💡 Sorted keys in action

Let’s add pairs with keys in a random order and watch the TreeMap sort them by key for us.

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> ages = new TreeMap<>();
        ages.put("Riya", 30);
        ages.put("Alex", 25);
        ages.put("Arjun", 28);

        System.out.println(ages);   // ✅ keys come out in alphabetical order
    }
}

What just happened:

• We added Riya, then Alex, then Arjun.
• The TreeMap stores them sorted by key, so printing gives Alex, Arjun, Riya.
• We never called any sort method ourselves.
• Looping would visit keys in that same sorted order, which a HashMap cannot promise.

{Alex=25, Arjun=28, Riya=30}

📒 A worked example: a sorted price list

Now let’s solve the shop problem from the start of the lesson. We keep a map from price to product name, and we let the TreeMap keep it sorted by price.

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

public class Main {
    public static void main(String[] args) {
        // ✅ key = price, value = product name
        TreeMap<Integer, String> priceList = new TreeMap<>();
        priceList.put(250, "Notebook");
        priceList.put(90, "Pen");
        priceList.put(700, "Headphones");
        priceList.put(150, "Mug");
        priceList.put(450, "Lamp");

        System.out.println("Full list, cheapest first:");
        for (Map.Entry<Integer, String> item : priceList.entrySet()) {
            System.out.println(item.getKey() + " -> " + item.getValue());
        }

        System.out.println("Cheapest item: " + priceList.firstEntry());
        System.out.println("Most expensive: " + priceList.lastEntry());
    }
}

What the code does:

• We inserted the products in a messy order.
• The loop over entrySet() still prints lowest price to highest, because the keys are sorted.
• firstEntry() hands back the whole cheapest pair, and lastEntry() the most expensive, each as one object instead of just the key.

Full list, cheapest first:
90 -> Pen
150 -> Mug
250 -> Notebook
450 -> Lamp
700 -> Headphones
Cheapest item: 90=Pen
Most expensive: 700=Headphones

This is the everyday win. No sorting code, no comparator at the call site, no copying keys into a list. The map was sorted the whole time.

🧭 Navigation methods

Because the keys are always sorted, a TreeMap answers order-based questions a HashMap cannot. These methods all work on the keys:

• firstKey() and lastKey() give the smallest and largest keys.
• higherKey(k) and lowerKey(k) give the next key strictly above or below k. The key k itself is skipped.
• ceilingKey(k) and floorKey(k) give the nearest key >= k or <= k. Here k itself counts if present.
• firstEntry() and lastEntry() give the smallest and largest pairs as whole entries, not just keys.
• The pair people mix up: higher/lower are strict (exclude the key you passed), ceiling/floor are inclusive (allow an exact match).

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> scores = new TreeMap<>();
        scores.put(50, "Alex");
        scores.put(70, "Riya");
        scores.put(90, "Arjun");

        System.out.println("Lowest score: " + scores.firstKey());
        System.out.println("Highest score: " + scores.lastKey());
        System.out.println("Just above 50: " + scores.higherKey(50)); // strict, skips 50
        System.out.println("Ceiling of 70: " + scores.ceilingKey(70)); // inclusive, allows 70
        System.out.println("Floor of 80: " + scores.floorKey(80));     // largest key <= 80
    }
}

Reading the results:

• higherKey(50) skips 50 and returns the next score up, 70.
• ceilingKey(70) allows an exact match, so it returns 70 itself.
• floorKey(80) finds the largest key not over 80, which is 70.
• These make a TreeMap great for “nearest match” lookups, like the price band a budget falls into. A HashMap offers none of this.

Lowest score: 50
Highest score: 90
Just above 50: 70
Ceiling of 70: 70
Floor of 80: 70

✂️ Range queries with subMap, headMap, and tailMap

The feature that really sets a TreeMap apart: you can grab a slice by key range. This is a range query, and only a sorted map does it cheaply.

• headMap(k) gives all pairs with keys below k.
• tailMap(k) gives all pairs with keys from k upward.
• subMap(from, to) gives all pairs from the low end up to, but not including, the high end.

Let’s reuse the price list and pull out the mid-range products, from 150 up to (but not including) 700.

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

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> priceList = new TreeMap<>();
        priceList.put(90, "Pen");
        priceList.put(150, "Mug");
        priceList.put(250, "Notebook");
        priceList.put(450, "Lamp");
        priceList.put(700, "Headphones");

        // ✅ keys from 150 (included) up to 700 (excluded)
        SortedMap<Integer, String> midRange = priceList.subMap(150, 700);
        System.out.println("Mid-range items: " + midRange);

        System.out.println("Budget options (under 250): " + priceList.headMap(250));
        System.out.println("Premium options (450 and up): " + priceList.tailMap(450));
    }
}

Reading the results:

• subMap(150, 700) returns Mug, Notebook, Lamp. 150 is included, 700 is left out: low bound in, high bound out.
• headMap(250) returns everything below 250.
• tailMap(450) returns 450 and everything above it.
• Each result is itself sorted, so you can loop or print it directly.

Mid-range items: {150=Mug, 250=Notebook, 450=Lamp}
Premium options (450 and up): {450=Lamp, 700=Headphones}
Budget options (under 250): {90=Pen, 150=Mug}

One detail worth knowing about these slices:

• They are views, not copies. They look at the original map.
• Put a new pair into the original that falls inside the range, and it shows up in the slice too.
• That makes range queries cheap. Treat the slice as a window onto the real data, not a snapshot.

⚖️ HashMap vs TreeMap vs LinkedHashMap

Java gives you three common maps, and choosing one is mostly about order. All three store unique keys and support put, get, and remove. The difference is the loop order and the cost. Here is the side-by-side.

Quick guidance:

• Reach for a HashMap by default when you just need fast lookups and order does not matter.
• Switch to a LinkedHashMap only when you want keys back in insertion order.
• Pick a TreeMap when you need sorted keys, navigation methods, or range queries.
• You pay a little speed for that power, so do not pick it out of habit.

⚠️ Common Mistakes

A few TreeMap slip-ups to watch for.

Using a custom key class without making it comparable. A TreeMap must order its keys, so a custom class as a key needs Comparable or a comparator. Skip it and the second put throws a ClassCastException, because Java tries to compare your object and cannot.

// ❌ Wrong: Product does not implement Comparable
class Product {
    String name;
    Product(String name) { this.name = name; }
}
TreeMap<Product, Integer> stock = new TreeMap<>();
stock.put(new Product("Pen"), 5);
stock.put(new Product("Mug"), 3); // ClassCastException here

// ✅ Right: teach the class its order with Comparable
class Product implements Comparable<Product> {
    String name;
    Product(String name) { this.name = name; }
    public int compareTo(Product other) {
        return this.name.compareTo(other.name); // sort by name
    }
}

Expecting insertion order. A TreeMap sorts by key and ignores the order you added pairs in. If you need insertion order, use a LinkedHashMap.

// ❌ Wrong tool if you expect "Riya, Alex, Arjun" back
TreeMap<String, Integer> ages = new TreeMap<>();
ages.put("Riya", 30);
ages.put("Alex", 25); // prints Alex first, not Riya

// ✅ Right tool when insertion order matters
LinkedHashMap<String, Integer> ordered = new LinkedHashMap<>();
ordered.put("Riya", 30);
ordered.put("Alex", 25); // prints Riya first

Using a null key. A HashMap allows one null key, a TreeMap does not. It cannot compare null against a real key, so it throws a NullPointerException.

TreeMap<String, Integer> map = new TreeMap<>();
map.put(null, 1); // ❌ NullPointerException
map.put("Alex", 1); // ✅ fine

Confusing key order with value order. A TreeMap sorts by keys, never by values. To sort by value, copy the entries into a list and sort with a comparator.

✅ Best Practices

Habits for using TreeMap well.

• Use a HashMap unless you actually need sorting or ranges. It is the faster default for plain lookups. A TreeMap earns its place only when order or range queries matter.
• Reach for it when keys must be sorted. Ordered reports, price bands, date-keyed logs, and sorted dictionaries are the natural fit.
• Use the navigation methods instead of scanning. firstKey, lastKey, floorKey, and ceilingKey answer “smallest,” “largest,” and “nearest” cleanly. Do not loop the whole map to find them.
• Use subMap, headMap, and tailMap for ranges. They are far cheaper and clearer than filtering by hand.
• Make custom keys comparable. Implement Comparable, or pass a Comparator to the constructor, so the TreeMap can order them.
• Guard against null returns. Methods like floorKey and higherKey return null when no match exists, so check before you use the result.

🧩 What You’ve Learned

Nicely done. Let’s recap TreeMap.

• ✅ A TreeMap stores key-value pairs with its keys kept in sorted order, automatically.
• ✅ It works like a map (unique keys, put/get) plus the ordering promise, and it is backed by a red-black tree, so put/get are O(log n).
• ✅ It adds navigation methods like firstKey, lastKey, higherKey, floorKey, and firstEntry.
• ✅ It supports range queries with subMap, headMap, and tailMap.
• ✅ Compared to HashMap and LinkedHashMap, it is a bit slower but keeps keys sorted and supports navigation and ranges.
• ✅ Its keys must be comparable and cannot be null (built-in types are comparable; custom keys need Comparable or a comparator).

🚀 What’s Next?

You now know the main collections. Java also ships a helper class full of ready-made tools for working with them, like sorting, reversing, and finding the max. Let’s finish the module with the Collections utility class.

Java Collections Utility Class