Unfortunately it seems like `TreeMap#map` doesn't even preserve ordering when explicitly typed:
```scala
scala> val tm = TreeMap[Int, String]()(Ordering.by((x: Int) => -x)) ++ Seq(1 -> "a", 2 -> "b", 3 -> "c")
tm: scala.collection.immutable.TreeMap[Int,String] = Map(3 -> c, 2 -> b, 1 -> a)

scala> val mapped = tm map identity
mapped: scala.collection.immutable.TreeMap[Int,String] = Map(1 -> a, 2 -> b, 3 -> c)
```
While `map` doesn't work, all the methods explicitly defined in `TreeMap`/`SortedMap` do preserve the ordering.