What is a TreeMap and how does it keep its keys sorted?
TreeMap stores entries in a red-black tree, a self-balancing binary search tree, ordered by the keys natural order or a supplied Comparator. get, put and remove take O(log n), and it offers range methods like firstKey and floorKey.
Explain it simply
A dictionary is sorted so you can flip to the right page quickly. A TreeMap keeps its keys in sorted order all the time, at the cost of a little work on every insert to keep the tree balanced.
Example
import java.util.*;
TreeMap<Integer, String> rank = new TreeMap<>();
rank.put(30, "Kohli");
rank.put(10, "Rohit");
rank.put(20, "Gill");
System.out.println(rank); // prints: {10=Rohit, 20=Gill, 30=Kohli}
System.out.println(rank.firstKey()); // prints: 10
System.out.println(rank.floorKey(25)); // prints: 20 (largest key <= 25)
System.out.println(rank.ceilingKey(25)); // prints: 30 (smallest key >= 25)What to say in the interview
"TreeMap is a red-black tree. Keys must be mutually comparable, either through Comparable or a Comparator I pass to the constructor, otherwise I get a ClassCastException. Operations are O(log n) instead of HashMap's O(1), but I get sorted iteration and navigation methods such as headMap, tailMap, floorKey and ceilingKey. It does not allow a null key with natural ordering."
Common mistakes
- Using a Comparator inconsistent with equals, so two different keys are treated as the same entry and one overwrites the other.