Explain the concept of TreeMap and how it is implemented in Java.

TreeMap in Java is an implementation of the NavigableMap interface that stores key-value pairs in sorted order by keys. It is based on a red-black tree — a balanced binary search tree that provides insertion, deletion, and search operations in O(log n).

Features of TreeMap:

• Keys are automatically sorted in natural order or with a Comparator if provided.
• Allows quick retrieval of subsets of keys, navigation methods (e.g., lowerKey, higherKey).
• Does not allow null as a key (unlike HashMap).

Example usage:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "Three");
map.put(1, "One");
map.put(2, "Two");

for (Integer key : map.keySet()) {
    System.out.println(key + " => " + map.get(key));
}
// Output will be sorted by keys: 1, 2, 3