Monday, March 24, 2014

Check if 2 trees are iso-morphic

Problem
Given 2 binary trees, check if they are isomorphic.
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.

Solution

C 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));
}
  

Thanks.

Reactions:

0 comments:

Post a Comment