Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've recently read this summary of the issues involved with doing diff between trees and it got me interested in learning what is the state of the art for this problem.

Also, suppose that between your allowed edit operations are the traditional add/delete node, edit content you add the extended operations of copy/move subtree, does this makes the problem (of finding an optimal diff) easier or harder?

share|cite|improve this question
up vote 14 down vote accepted

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):

share|cite|improve this answer

A useful survey on the topic, slightly out of date:

Philip Bille. A survey on tree edit distance and related problems. Theoretical Computer Science, Volume 337, Issues 1–3, Pages 217–239, 2005.

A recent paper on one of the versions of the problem:

Tatsuya Akutsu et al. Exact algorithms for computing the tree edit distance between unordered trees. Theoretical Computer Science, Volume 412, Issues 4–5, Pages 352–364, 2011.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.