  Computing the edit distance of two strings is one of the most basic problems
in computer science and combinatorial optimization. Tree edit distance is a
natural generalization of edit distance in which the task is to compute a
measure of dissimilarity between two (unweighted) rooted trees with node
labels. Perhaps the most notable recent application of tree edit distance is in
NoSQL big databases, such as MongoDB, where each row of the database is a JSON
document represented as a labeled rooted tree, and finding dissimilarity
between two rows is a basic operation. Until recently, the fastest algorithm
for tree edit distance ran in cubic time (Demaine, Mozes, Rossman, Weimann;
TALG'10); however, Mao (FOCS'21) broke the cubic barrier for the tree edit
distance problem using fast matrix multiplication.
  Given a parameter $k$ as an upper bound on the distance, an $O(n+k^2)$-time
algorithm for edit distance has been known since the 1980s due to the works of
Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88). The existence of an
$\tilde{O}(n+\mathrm{poly}(k))$-time algorithm for tree edit distance has been
posed as an open question, e.g., by Akmal and Jin (ICALP'21), who gave a
state-of-the-art $\tilde{O}(nk^2)$-time algorithm. In this paper, we answer
this question positively.
