TreeMap | Engineering Interview Kit

TL;DR

TreeMap implements the NavigableMap and SortedMap interfaces.
It stores key-value pairs sorted in ascending order of the keys.
It provides $O(\log n)$ performance for containsKey, get, put, and remove.
It does not allow null keys.

Concept

Under the hood, TreeMap is implemented as a Red-Black Tree (a self-balancing binary search tree). Because it relies on tree nodes being strictly smaller or larger than one another, the keys must be comparable.

Like TreeSet, sorting is determined either by the keys’ natural ordering (must implement Comparable) or by a Comparator provided at map creation time.

Examples

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        
        // Natural Ordering (Alphabetical keys)
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("Charlie", 85);
        scores.put("Alice", 92);
        scores.put("Bob", 78);
        
        // Will print in order: Alice, Bob, Charlie
        System.out.println(scores); 
        
        // NavigableMap Methods
        System.out.println("Lowest Key: " + scores.firstKey()); // Alice
        System.out.println("Highest Key: " + scores.lastKey()); // Charlie
        
        // Get the closest key greater than or equal to "B"
        System.out.println("Ceiling for B: " + scores.ceilingKey("B")); // Bob
        
        // Custom Ordering (Descending)
        TreeMap<Integer, String> ids = new TreeMap<>((a, b) -> b.compareTo(a));
        ids.put(1, "A");
        ids.put(3, "C");
        ids.put(2, "B");
        System.out.println(ids.keySet()); // [3, 2, 1]
    }
}

Interview Questions

Q: Can a TreeMap have null values?
A: Yes. A TreeMap can have as many null values as you want. It simply cannot have null keys, because it needs to compare keys against each other to sort them in the tree, and calling .compareTo() on null throws a NullPointerException.

Q: When should you use TreeMap vs HashMap?
A: Use HashMap for general-purpose key-value storage; it is $O(1)$ and much faster.
Use TreeMap only when you explicitly need the keys to be iterated in a sorted order, or when you need to perform range-based queries (e.g., “give me all keys between 50 and 100”).