# Rooted Tree Isomorphism Algorithm

I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture:

Let $$S_{u}$$ be the number of vertices in the rooted subtree of vertex $$u$$. Namely, the size of the subtree of $$u$$. Now Let $$L_{i}$$ = {$$S_{u}$$ : $$lvl(u)$$ = $$i$$}. Here, $$lvl(v)$$ denotes the level of $$v$$. Also the height of a tree is the maximum level of any of its nodes.

Now the conjecture:

Let $$H_{1}$$ and $$H_{2}$$ be the heights of the rooted trees $$T_{1}$$ and $$T_{2}$$, respectively. $$T_{1}$$ and $$T_{2}$$ are isomorphic if and only if $$H_{1} = H_{2}$$ and for every integer $$i \in [ \,1,H_{1}] \,$$, the multiset $$L_{i}$$ of $$T_{1}$$ and that of $$T_{2}$$ are the same.

Apparently this conjecture is false because i implemented a C++ program (to solve a competitive programming task) that is based on it, but it failed system tests. Still, it may be an implementation fault, so i'd like to know if there are any counterexamples to this conjecture.

• Yeah, that`s what i meant. – Mateus Buarque Mar 13 '19 at 14:36

## 1 Answer

Nice conjecture on tree isomorphism. Here is a counterexample.  Exercise. Construct a counterexample using a binary tree.

• Thanks, guess i'll have to code AHU anyways. – Mateus Buarque Mar 13 '19 at 15:34
• I don't think it's possible to do so, at least not with the same approach you used on your counterexample. That's because at the level above the leafs you can only have 1 or 2 as a subtree size, so any shuffling between those that maintains the sum of the subtree of nodes above would result in two parts that are congruent to the previous two (before you shuffled). – Mateus Buarque Mar 13 '19 at 15:51
• @MateusBuarque Here is a hint for the exercise. The answer is simple based on the given counterexample. – John L. Mar 13 '19 at 16:08
• Finally found it! – Mateus Buarque Mar 13 '19 at 17:22