We'll use the famous animal tree:

Reptile - Snake - Python
                - Cobra
        - Lizard - Salamander
                 - Chameleon
        - Bird - Pigeon
               - Canary
               - Owl
Mammal - Equine - Horse
                - Zebra
                - Pony
       - Canine - Dog
                - Fox
                - Wolf
       - Bovine - Cow
                - Bison
[download]

All the leaves are on the same level.

Let's have a module Zoo.pm which implements the following methods:

Parent

Static method. 'Zoo'->Parent($node) returns the parent of the given node in the tree, e.g. 'Zoo'->Parent('Owl') is 'Bird', 'Zoo'->Parent('Bird') is 'Reptile'.

new

The constructor. Use a list of tree leaves as arguments:

my $zoo = 'Zoo'->new(qw( Cobra Pigeon Zebra ));
[download]

get_leaves

For a given object, returns the list it was constructed from (order is not guaranteed).

print join ' ', $zoo->get_leaves;  # Cobra Pigeon Zebra
[download]

The Task

When comparing too different zoos, we aren't interested in the animals only, but in their categories, too. Our task is to implement a static method 'Zoo'->diff($zoo1, $zoo2) which returns two array references, $add and $delete, such that:

1. Imagine we build trees above both of the objects, containing all their $_->get_leaves and their ancestors.
2. If we start from the tree built above $zoo1, add all the nodes from $add and remove all nodes from $delete, we get $zoo2.
3. Both the lists @$add and @$delete are minimal.

For example,

'Zoo'->diff( 'Zoo'->new('Cobra'),
             'Zoo'->new('Fox')
           )
[download]

should return

( [qw[ Fox Canine Mammal ]],
  [qw[ Cobra Snake Reptile ]]
)
[download]

Similarly,

'Zoo'->diff( 'Zoo'->new(qw( Dog Fox Wolf )),
             'Zoo'->new(qw( Fox )));
[download]

should return

( [],
  [ 'Dog', 'Wolf' ]
)
[download]

Updates: Please, use <readmore> tags for the code.

Use only the documented API in the solution (i.e. Parent and get_leaves). The tree structure is not accessible directly (in reality, it was stored in a database).

($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord
}map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
[download]