Question: Two binary trees s and t are isomorphic if they have the same shape; the values stored in the nodes do not affect whether two trees are isomorphic. In the diagram below, the tree in the middle is not isomorphic to the other trees, but the tree on the right is isomorphic to the tree on the left. Write a method isIsomorphic that returns true if its two tree parameters are isomorphic and false otherwise.
Code:
bool isomorphic(struct treenode *treeone, struct treenode *treetwo)
{
if (!treeone && !treetwo)
return true;
if((!treeone && treetwo) || (treeone && !treetwo))
return false;
return (isomorphic(treeone->left, treetwo->left)
&& isomorphic(treeone->right, treetwo->right));
}
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
This is not correct u just check for ((a+b)+c) and (c+(a+b)) is isomorphic but it shows it is not isomorphic....................
@nima: As far as I understood by tree ((a+b)+c) and (c+(a+b)), these are Quasi-Isomorphic Trees and not Isomorphic.
@nima: If you are still feel that it's not correct, can you please provide me the complete tree structure?
I think you need to check again if all of the trees(the three that in the picture) aren't isomorphic to each other. [I am based on opinion of a Course Coordinator in the University i learning at]. Trees are isomorphic to each other is that if you get one them by changing the second by a series of operations where you choose a certain node and changing between his sons pointers.
More clear explanation of the mistake is : Two trees are isomorphic if they are the same or one can be obtained from the other by a series of flips. A flip across a node is swapping its left and right subtrees.