Why is this hard?
Trees are many!
(my failed proof)
The Split Theorem
The merge and sort trick
Efficient polynomial algorithm?
$\frac{1}{2} \log_3 \frac{(n-1)!n!}{6^{n-1}} \leq \mathrm{Diam} \leq n^2 - 3n - \frac{5}{8}$
Introduced the RNNI graph on ranked trees (to the best of our knowledge)
Established basic geometric properties of the graph
Designed an efficient approximate algorithm for computing shortest paths
Proved that all the fancy NNI methods, e.g. Sleator-Tarjan-Thurston and merge-and-sort argument, don't work
Failed to prove that RNNI is NP-hard
Hence, time trees are (more or less) fine
[Stadler, JTB 2010] must be cheating then :)