Calculate minimal operations to make two tree structures identical

Tomas Vana picture Tomas Vana · May 5, 2011 · Viewed 29.6k times · Source

This is more of a CS question, but an interesting one :

Let's say we have 2 tree structures with more or less the same nodes reorganized. How would you find

  1. any
  2. in some sense minimal

sequence of operations

  • MOVE(A, B) - moves node A under node B (with the whole subtree)
  • INSERT(N, B) - inserts a new node N under node B
  • DELETE (A) - deletes the node A (with the whole subtree)

that transforms one tree to the other.

There might obviously be cases where such transformation is not possible, trivial being root A with child B to root B with child A etc.). In such cases, the algorithm would simply deliver an result "not possible".

Even more spectacular version is a generalization for networks, i.e. when we assume that a node can occur multiple times in the tree (effectively having multiple "parents"), while cycles are forbidden.

Disclaimer : This is not a homework, actually it comes from a real business problem and I found it quite interesting wondering if somebody might know a solution.

Answer

Andre Holzner picture Andre Holzner · May 5, 2011

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: