O TreeMap ordena os elementos por chave ao adicioná-los?

Sim, o TreeMap em Java armazena elementos em ordem classificada por chave. Ao adicionar um novo elemento, o TreeMap usa ou a ordem natural das chaves (se as chaves implementarem Comparable) ou um comparador (Comparator) fornecido, para determinar a posição de inserção.

Assim, os elementos estão sempre ordenados, e as operações de busca, inserção e remoção são realizadas com complexidade logarítmica.

Exemplo:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "três");
map.put(1, "um");
map.put(2, "dois");

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