In trying to solve the problem involving tree isomorphism, I came across a paper explaining an algorithm for checking if two trees are isomorphic.

However, I cannot understand the complexity analysis of the AHU algorithm described in the paper. Why is the worst case O(N^2). It seems to me that when we go down in the tree the lengths of all the string we need to sort is decreasing as well, and hence we are dealing with something O(NlogN).

My second question is about the improvement part (section 4.3 AHU algorithm improvement). I don't understand what the author means by sorting by level, and how can we convert those strings (canonical names) to integers.

Hope that someone could help me. Thanks in advance.