  Tree edit distance is a well-studied measure of dissimilarity between rooted
trees with node labels. It can be computed in $O(n^3)$ time [Demaine, Mozes,
Rossman, and Weimann, ICALP 2007], and fine-grained hardness results suggest
that the weighted version of this problem cannot be solved in truly subcubic
time unless the APSP conjecture is false [Bringmann, Gawrychowski, Mozes, and
Weimann, SODA 2018].
  We consider the unweighted version of tree edit distance, where every
insertion, deletion, or relabeling operation has unit cost. Given a parameter
$k$ as an upper bound on the distance, the previous fastest algorithm for this
problem runs in $O(nk^3)$ time [Touzet, CPM 2005], which improves upon the
cubic-time algorithm for $k\ll n^{2/3}$. In this paper, we give a faster
algorithm taking $O(nk^2 \log n)$ time, improving both of the previous results
for almost the full range of $\log n \ll k\ll n/\sqrt{\log n}$.
