¿TreeMap ordena los elementos por clave al agregarlos?

Sí, TreeMap en Java almacena los elementos en orden ordenado por la clave. Al agregar un nuevo elemento, TreeMap utiliza ya sea el orden natural de las claves (si las claves implementan Comparable) o un comparador (Comparator) proporcionado, para determinar la posición de inserción.

De esta manera, los elementos siempre están ordenados, y las operaciones de búsqueda, inserción y eliminación se realizan con complejidad logarítmica.

Ejemplo:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "tres");
map.put(1, "uno");
map.put(2, "dos");

System.out.println(map.keySet()); // [1, 2, 3]