TreeMap in Java

Analogy categoryAnalogies

1. Introduction

TreeMap is an implementation of the Map interface (specifically the NavigableMap/SortedMap sub-interfaces) that keeps its keys in sorted order — either natural ordering (via Comparable) or a custom order supplied via a Comparator.

🏏

Cricket analogy: TreeMap is like a batting order automatically sorted by average — either natural order (highest average first) or via a custom Comparator such as strike rate, unlike a random substitute list.

Internally, TreeMap is backed by a Red-Black tree, a type of self-balancing binary search tree. This guarantees O(log n) time complexity for get(), put(), and remove(), trading some raw speed for guaranteed order.

🏏

Cricket analogy: Like a well-organized knockout bracket that stays balanced so you never need more than a handful of rounds to find a team, TreeMap's Red-Black tree keeps lookups to O(log n) instead of scanning every match.

2. Syntax

text

TreeMap<String, Integer> map = new TreeMap<>(); // natural order
TreeMap<String, Integer> customOrder =
    new TreeMap<>(Comparator.reverseOrder());     // custom order

map.put("banana", 2);
map.put("apple", 1);
map.firstKey();
map.lastKey();
map.higherKey("apple");

3. Explanation

Unlike HashMap, which offers average O(1) but unordered access, TreeMap guarantees keys are always iterated in sorted order at the cost of O(log n) for get/put/remove operations — a direct trade-off between speed and ordering. TreeMap also does not permit a null key (it needs to compare keys, and comparing against null throws a NullPointerException), though it does allow multiple null values.

🏏

Cricket analogy: Unlike a random pile of scorecards (HashMap's O(1) but unordered access), TreeMap always keeps the batting order sorted at O(log n) cost, and it refuses a nameless batsman as a key since it can't compare against null, though an unrecorded score value is fine.

Because it implements NavigableMap, TreeMap provides powerful navigation methods like firstKey(), lastKey(), higherKey(), lowerKey(), ceilingKey(), and floorKey(), which HashMap does not offer.

🏏

Cricket analogy: TreeMap's firstKey()/lastKey() are like instantly naming the top and bottom of the batting averages list, while higherKey()/lowerKey()/ceilingKey()/floorKey() find the nearest average just above or below a given player's — HashMap can't do any of this.

Contrast: HashMap = O(1) average, unordered. TreeMap = O(log n), always sorted. Choose based on whether you need speed or guaranteed ordering.

4. Example

java

import java.util.*;

public class TreeMapDemo {
    public static void main(String[] args) {
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("Charlie", 85);
        scores.put("Alice", 92);
        scores.put("Bob", 78);

        System.out.println("Sorted map: " + scores);
        System.out.println("First key: " + scores.firstKey());
        System.out.println("Last key: " + scores.lastKey());
        System.out.println("Higher than 'Alice': " + scores.higherKey("Alice"));
    }
}

5. Output

text

Sorted map: {Alice=92, Bob=78, Charlie=85}
First key: Alice
Last key: Charlie
Higher than 'Alice': Bob

6. Key Takeaways

TreeMap keeps keys sorted using a Red-Black tree.
get(), put(), remove() run in O(log n) time.
Contrast with HashMap: O(1) average but unordered, vs TreeMap's O(log n) but sorted.
TreeMap does not allow a null key, but allows null values.
Provides navigation methods: firstKey(), lastKey(), higherKey(), lowerKey().