Calculate minimal operations to make two tree structures identical
There is not only a Wikipedia article on graph isomorphism (as Space_C0wb0y points out) but also a dedicated article on the graph isomorphism problem. It has a section Solved special cases for which polynomial-time solutions are known. Trees is one of them and it cites the following two references:
- P.J. Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957) pp. 961–968
- Aho, Alfred V.; Hopcroft, John; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Reading, MA: Addison–Wesley .
Although this question is old, i'll add a couple more references and algorithms below:
- X-Diff: An Effective Change Detection Algorithm for XML Documents , Yuan Wang, David J. DeWitt, Jin-Yi Cai
- KF-Diff+: Highly Efficient Change Detection Algorithm for XML Documents
- diffX: An Algorithm to Detect Changes in Multi-Version XML Documents
- Change Detection in XML Trees: a Survey, Luuk Peters
- Similarity in Tree Data Structures
Furthermore, there are libraries and frameworks on GitHub (in javascript) which implement diffing of Tree-like structures for example applications dealing with JSON data or XML Trees (e.g for client-side MVC/MVVM):
- React.js
- JSON-Patch
- jsondiffpatch
- objectDiff
You weren't clear if you were comparing abstract syntax trees for source code, XML documents interpreted as trees, or some other type of tree.
There's a number of papers that discuss comparing syntax trees and computing minimum distances by various means. The ideas should be relevant.
A good paper is Change Distilling, which tries to compare the source code for two abstract syntax trees and report a minimal difference. The paper talks about a specific method, and also briefly mentions (and provides references) to a variety of similar techniques.
Few of these algorithms are actually realized in available tools for comparing computer program source text. Our Smart Differencer is one of them; it is driven by an explicit language grammar for many languages.