Question: Two trees s and t are quasi-isomorphic if s can be transformed into t by swapping left and right children of some of the nodes of s. The values in the nodes are not important in determining quasi-isomorphism, only the shape is important. The trees below are quasi-isomorphic because if the children of the nodes A, B, and G in the tree on the left are swapped, the tree on the right is obtained. Write a method isQuasiIsomorphic that returns true if two trees are quasi-isomorphic.



Code:

  
bool quasiisomorphic(struct treenode *treeone, struct treenode *treetwo)
{
if (!treeone && !treetwo)
return true;
if((!treeone && treetwo) || (treeone && !treetwo))
return false;

return (quasiisomorphic(treeone->left, treetwo->left)
&& quasiisomorphic(treeone->right, treetwo->right)
|| quasiisomorphic(treeone->right, treetwo->left)
&& quasiisomorphic(treeone->left, 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.