efficient diff algorithm for trees and Levenshtein distance
The following paper describes a slightly more efficient algorithm than Zhang-Shasha for computing tree edit distance, along with a proof that their algorithm is optimal (within a certain broad class of algorithms):


Erik Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann.  An Optimal Decomposition Algorithm for Tree Edit Distance.  ACM Transactions on Algorithms, 6(1), 2009.