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