Synopsys R&D Interview Question
Senior Software Development EngineersCountry: India
1. do tree traversal
2. if any of them hits the NULL after the leaf node then chek for another one doing the same or not.
int flag = 0;
bool chekSimilatTree( tree1 root1, tree2 root2) {
if( (root1==NULL && root2!=NULL) || (root2==NULL && root1!=NULL) ) {
flag=1; return ;
}
if (root1==NULL && root2==NULL )
return ;
chekSimilarTree ( root1->left, root2->left);
chekSimilarTree( root1->right, root2->right );
if( flag==1 )
return false;
else return true;
}
If structurally similar means : in binary tree the alignment of tree is same but values can be different then...
int strSimilar(struct node *root1,struct node *root2)
{
if(root1==NULL && root2==NULL)
return 1;
if(root1==NULL || root2== NULL)
return 0;
return strSimilar(root1->left,root2->left) && strSimilar(root1->right,root2->right);
}
If we are talking about a binary tree shape similarity, then the below code does it (descriptions inlined):
- ashot madatyan June 23, 2013