Home/Learn/Java A–Z/TreeMap

TreeMap

Intermediate
Collections Framework

A sorted Map backed by a Red-Black tree — O(log n) operations plus powerful range-query methods like floorKey, ceilingKey, subMap, and headMap.

Overview

TreeMap implements NavigableMap (which extends SortedMap) using a Red-Black tree internally. Every operation — get, put, remove, containsKey — is O(log n). Keys are kept in sorted order at all times, either by their natural ordering (Comparable) or a custom Comparator supplied at construction. This sorted structure unlocks a rich set of range-query methods unavailable in HashMap, making TreeMap the go-to choice whenever you need sorted keys, range scans, or nearest-key lookups.

Basic Operations & Natural Ordering

TreeMap requires that keys be mutually comparable. If you use a class that does not implement Comparable and provide no Comparator, the first put() throws ClassCastException. String, Integer, and most JDK types implement Comparable.

Key characteristic: iterating a TreeMap (keySet, entrySet, values) always returns elements in ascending key order. This is a guarantee — not a coincidence.

TreeMapBasics.java
import java.util.*;

public class TreeMapBasics {
    public static void main(String[] args) {
        // Natural ordering (String Comparable — alphabetical)
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("Charlie", 88);
        scores.put("Alice",   95);
        scores.put("Bob",     82);
        scores.put("Diana",   91);

        // Always iterates in sorted key order
        scores.forEach((k, v) -> System.out.println(k + " → " + v));
        // Alice → 95 | Bob → 82 | Charlie → 88 | Diana → 91

        System.out.println(scores.firstKey()); // Alice
        System.out.println(scores.lastKey());  // Diana

        // SortedMap views (still backed by original)
        SortedMap<String, Integer> bToD = scores.subMap("Bob", "Diana");
        System.out.println(bToD); // {Bob=82, Charlie=88}  — "Diana" exclusive

        SortedMap<String, Integer> upToC = scores.headMap("Charlie");
        System.out.println(upToC); // {Alice=95, Bob=82}   — "Charlie" exclusive

        SortedMap<String, Integer> fromC = scores.tailMap("Charlie");
        System.out.println(fromC); // {Charlie=88, Diana=91}

        // Custom Comparator — reverse order
        TreeMap<String, Integer> reversed = new TreeMap<>(Comparator.reverseOrder());
        reversed.putAll(scores);
        System.out.println(reversed.firstKey()); // Diana
    }
}

NavigableMap — Floor, Ceiling, Higher, Lower

NavigableMap adds nearest-key lookups that are very useful for scheduling, range buckets, and interval problems:

floorKey(k) — greatest key ≤ k (or null) ceilingKey(k) — smallest key ≥ k (or null) lowerKey(k) — greatest key strictly < k higherKey(k) — smallest key strictly > k pollFirstEntry() / pollLastEntry() — remove and return the boundary entry descendingMap() — reversed view

These all run in O(log n).

NavigableMapDemo.java
import java.util.*;

public class NavigableMapDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "ten");
        map.put(20, "twenty");
        map.put(30, "thirty");
        map.put(40, "forty");
        map.put(50, "fifty");

        // Nearest-key lookups
        System.out.println(map.floorKey(25));   // 20 — greatest ≤ 25
        System.out.println(map.ceilingKey(25)); // 30 — smallest ≥ 25
        System.out.println(map.lowerKey(30));   // 20 — strictly < 30
        System.out.println(map.higherKey(30));  // 40 — strictly > 30
        System.out.println(map.floorKey(5));    // null — nothing ≤ 5

        // Inclusive/exclusive subMap
        NavigableMap<Integer, String> sub = map.subMap(20, true, 40, true);
        System.out.println(sub); // {20=twenty, 30=thirty, 40=forty}

        // Poll — remove and return boundary entries
        Map.Entry<Integer, String> first = map.pollFirstEntry();
        System.out.println(first);  // 10=ten
        Map.Entry<Integer, String> last = map.pollLastEntry();
        System.out.println(last);   // 50=fifty
        System.out.println(map);    // {20=twenty, 30=thirty, 40=forty}

        // Descending view
        System.out.println(map.descendingMap()); // {40=forty, 30=thirty, 20=twenty}

        // Practical: find the price tier for a given score
        TreeMap<Integer, String> tiers = new TreeMap<>();
        tiers.put(0,  "Bronze");
        tiers.put(50, "Silver");
        tiers.put(80, "Gold");
        tiers.put(95, "Platinum");
        System.out.println(tiers.floorEntry(72).getValue()); // Silver
        System.out.println(tiers.floorEntry(95).getValue()); // Platinum
    }
}

TreeMap vs HashMap — When to Use Which

HashMap O(1) average — use when order does not matter and you need maximum throughput. TreeMap O(log n) — use when you need: • Keys always in sorted order • Range queries (subMap, headMap, tailMap) • Nearest-key lookups (floor, ceiling) • Predictable iteration order

Common interview pattern: use TreeMap to implement a time-based event scheduler, a sliding-window frequency map, or a price-tier lookup table.

EventScheduler.java
import java.util.*;

// Real-world: event scheduler using TreeMap
public class EventScheduler {
    // Key: timestamp (Long), Value: event description
    private final TreeMap<Long, String> schedule = new TreeMap<>();

    public void addEvent(long timestamp, String event) {
        schedule.put(timestamp, event);
    }

    // Get the next event at or after 'now'
    public Map.Entry<Long, String> nextEvent(long now) {
        return schedule.ceilingEntry(now);
    }

    // Get all events in a time range [start, end]
    public NavigableMap<Long, String> eventsInRange(long start, long end) {
        return schedule.subMap(start, true, end, true);
    }

    public static void main(String[] args) {
        EventScheduler scheduler = new EventScheduler();
        long base = System.currentTimeMillis();
        scheduler.addEvent(base + 1000, "Meeting");
        scheduler.addEvent(base + 3000, "Lunch");
        scheduler.addEvent(base + 7200, "Review");

        Map.Entry<Long, String> next = scheduler.nextEvent(base + 2000);
        System.out.println("Next event: " + next.getValue()); // Lunch

        NavigableMap<Long, String> afternoon =
            scheduler.eventsInRange(base + 2000, base + 8000);
        System.out.println("Afternoon events: " + afternoon.values());
        // [Lunch, Review]
    }
}

Interactive Visualization

«I»Collection
«I»List
«I»Set
«I»Queue
Collection is the root interface. It branches into List, Set, and Queue.
1 / 5

Key Points to Remember

  • TreeMap is backed by a Red-Black tree — all ops are O(log n); HashMap is O(1) average
  • Keys must implement Comparable or a Comparator must be provided at construction
  • Iteration always returns keys in sorted ascending order
  • floorKey/ceilingKey/lowerKey/higherKey enable O(log n) nearest-key lookups
  • subMap/headMap/tailMap return live views — changes to the view affect the original
  • Ideal for: sorted key iteration, range scans, event schedulers, price-tier lookups

Practice TreeMap in the Playground

Run and modify code directly in your browser - no setup needed.

Interview Questions

Sign in to ask Aria
1

What is the internal data structure of TreeMap?

MediumAmazon
2

What is the difference between TreeMap and HashMap?

MediumGoogle
3

What is the difference between floorKey() and lowerKey() in TreeMap?

MediumOracle
4

What happens if you put a non-Comparable key into a TreeMap with no Comparator?

MediumMicrosoft
5

How would you implement an LRU cache using LinkedHashMap vs TreeMap?

HardUber

Ask Aria about TreeMap

Your personal AI tutor — ask anything about this concept

Previous
HashMap
Next
HashSet & LinkedHashSet