Two trees (we will only binary trees) are isomorphic if you can perform some number of swaps between left and right siblings to achieve the same tree.

So for instance the following trees are isomorphic

1 / \ / \ 2 5 /\ 3 4 1 / \ / \ 5 2 / \ 3 4

but the flowing are not

1 / \ / \ 2 5 /\ 3 4 1 / \ / \ 2 5 / \ 3 4

Your challenge is to write an algorithm that checks to see if two trees are isomorphic and then explain what the running time is and why. You may either consider balanced binary trees or unbalanced binary trees. You shouldn't need to consider balanced trees however but it allows for a different argument if you have that assumption.

There is a natural solution to this problem that looks something like the following (in spoiler tags so you can come up with your own).

Spoiler

My immediate thought was that this algorithm was very very slow. I thought it had exponential running time. Why does it not have exponential running time? Also tell my what your intuitions were when you first saw this problem (be it here or elsewhere). Mine personally were wrong but depending on how you look at this it could actually be very obvious. Which camp were you in?

This post has been edited by **ishkabible**: 15 September 2015 - 08:43 AM