algorithm - How can i diff two trees to determine parental changes? -

i've got tree structure need rearrange (drag , drop) , submit changes.

what's going best way capture changes? see there 2 ways,

1. store every change command, submit list of changes execute each one
2. serialize tree , diff new tree old tree work out whats changed, execute changes

1 seems easiest implement, although wasteful if many repetitive actions have occurred (i.e. dragging nodes around many times, putting them started)

2 avoids above problem, how can "diff" trees work out parental change commands execute? presumably there algorithms this?

edit clarify, every node has "id" , "parentid". need allow users rearrange tree (thereby changing parentid of nodes).

for option 2, should straightforward enough serialize changed tree, work out differences iterate on the original tree in preorder, find same node in new tree , record change if parents different? robust approach wont stuck in cycle?

edit no, wont work. need iterate on new tree in preorder , find corresponding node in old tree, diff parent ids etc..

thanks

unless trees huge might easiest delete old tree , add new tree.

differencing 2 trees when allowed operations include moves, deletes, adds going more complex unless there significant benefit gained it's best avoid complexity , use simple remove-then-add option.