How do I calculate tree edit distance?
algorithm, tree
Solution
Here's some Java source code (gzipped tarball at the bottom) for a tree edit distance algorithm that might be useful to you.
The page includes references and some slides that go through the "Zhang and Shasha" algorithm step-by-step and other useful links to get you up to speed.
The code in the link has bugs. Steve Johnson and tim.tadh have provided working Python code. See Steve Johnson's comment for more details.
Problem
I need to calculate the edit distance between trees. This paper describes an algorithm, but I can't make heads or tails out of it. Could you describe an applicable algorithm in a more approachable way? Pseudocode or code would both be helpful.