Wednesday, November 7, 2012

IsoMorphic Binary Trees


Two trees can be called isomorphic if they have similar structure and the only difference amongst them can be is, that their child nodes may or may not be swapped..

For example


The trees in the above picture are called  Isomorphic Trees.The following code checks whether two trees are Isomorphic or not.

Code:(Written in C)

int is_isomorphic(struct node *t1,struct node *t2)
{
if(t1==NULL && t2==NULL)
            return 1;
if(t1==NULL || t2==NULL || t1->data!=t2->data)
return 0;
return  (is_isomorphic(t1->left,t2->left)&&is_isomorphic(t1->right,t2->right) || is_isomorphic(t1->left,t2->right)&&is_isomorphic(t1->right,t2->left) );
}

Please let me know if u have any questions


No comments: