Check if two trees are equivalent

Question

The following are three equivalent representations of the same tree (phylogenetic). I am trying to figure out an algorithm to check if two tree representations are equivalent. Trees are defined to be equivalent if the parent-child relationship between nodes are similar.

(Whale,(Seal,((Mouse,Rat),((((Carp,Loach),Frog),Chicken),Human))),Cow);
(Whale,(Seal,((Rat,Mouse),(Human,((Frog,(Loach,Carp)),Chicken)))),Cow);
((Seal,((Rat,Mouse),(Human,((Frog,(Loach,Carp)),Chicken)))), Cow, Whale);

Can anyone suggest a method?

Answer 1

One way would be to walk the children in lexographical order (or any strict weak ordering) and compare.

Answer 2

You can write each edge twice - once as (a,b) and once as (b,a) for both trees. For instance produce two strings for (Mouse, Rat): "Mouse : Rat" and "Rat : Mouse" then write all these strings, sort them lexicographically and compare the two lists. If they are the same then the trees are similar. This is different to Andrew Tomazos's solution as it will say that a tree is similar to itself traversed bottom to top i.e. it supports edge reversals.

Answer 3

Check the inorder and postorder traversal of both the trees.If they are same then those two trees are same