Described is a method and system for comparing two XML documents, usually
represented as two logical dependency trees, and providing their
differences as a set of tree operations. The set of tree operations may
be used to transform one tree to the other. A first phase constructs an
XML tree of nodes for each file, and a second, link tree construction
phase builds a tree of link objects that relate nodes in the left tree to
nodes in the right tree. Construction of the link tree generally operates
by mapping equal subtrees in the left and right trees to each other,
linking mapped subtrees to each other, removing any crossing links,
linking groups, and filling gaps in the link tree. A third output phase
uses the link tree to write an output file, such as comprising an XML
document of change (e.g., insert and delete) operations.