Algorithm to find difference between two uniquely labeled general trees

Question

I'm looking for an algorithm that finds the minimal changes (insert, delete, move) to get from tree1 to tree2.

The tree is a general and uniquely labeled tree. This means that each node's value is some kind of unique identifier, like a UUID. Each node can have children and the order of those child nodes is important. Example tree 1

A
 - B
 - C
   - D
   - E
 - F

Example tree 2

A
 - B
 - F
  - C
    - D
 - G

expected changes from tree 1 to tree 2

move(atIndex: 1, inParent: A, toIndex: 0, inParent: F)
delete(atIndex: 1, inParent: C)
insert(atIndex: 2, inParent: A)

I need this for a macOS App to animated changes in an NSOutlineView. I found some algorithms to find changes between general trees, but only for ordered and labeled trees and none for uniquely labeled trees. The algorithms for non-uniquely labeled trees semes to be really complex and I thought that if the labels are unique there must be a simpler and more efficient algorithm.

BTW: NSOultineView does not have a root node but an array of nodes at the beginning. I don't know if that's important.

Answer 1

You're right -- label uniqueness does simplify the problem.

For each label present in both trees, compute a sequence of operations to edit its children. This involves computing a longest common subsequence and issuing appropriate moves/inserts/deletes for all nodes not in this subsequence. (In case a label is present in both trees but with different parents, we should suppress the delete for the old parent.)

This set of operations constitutes a lower bound, but if we just do them, we may hit a situation where we try to move a node under one of its descendants. Perhaps it's enough to detect when this is about to happen and split it into two moves. If you really need the optimal sequence of moves, then I think there's a feedback arc/node set problem to be solved, though it might not be NP-hard here due to the tree structure.

Answer 2

Given that labels are unique, I'm not convinced that "minimal" changes are any different than outlining the diff for each node's full path.

If we look at the path from right to left, we can see that the first parent and index of D below didn't change.

It seems like the minimal changes provided in the question description make an assumption that the move of F from index 2 to 1 happens magically when C at 1 moves. But rather the two actions of "move C" and "move F to C's former place," which we would get from just examining the paths, comprise the actual behaviour that would need to occur due to the assumption in your current "move C."

Example tree 1
A        ⊥
 - B     A 0
 - C     A 1
   - D   A C 0
   - E   A C 1
 - F     A 2
 
Example tree 2
A          ⊥
 - B       A 0
 - F      *A 1
   - C    *A 1 F 0
     - D  *A 1 F 0 C 0
 - G       A 2