Subset trees

Given a big tree and a small tree, give an algo to find if the small tree is a subset of the big tree.

Solution 1:

//Time Complexity : O(mn) , where is m and n are the number of nodes in the trees.
bool isSubtree(Node* bigTree, Node* smallTree)
{
    if(!bigTree && !smallTree)
        return true;
    else if( (!bigTree && smallTree) ||
            (bigTree && !smallTree)
           )
        return false;

    if ( bigTree->node == smallTree->node )
    {
        /* If the node value matches, then check the left and right
         * subtrees
         * */
        bool isLeftSubTree = isSubtree (bigTree->left, smallTree->left);
        if (isLeftSubTree)
            isRightSubTree = isSubtree (bigTree->right, smallTree->right);
        if (isLeftSubTree && isRightSubTree )
            return true;
    }
    /* we need to check in left subtree and right subtree */
    isLeftSubTree = isSubtree(bigTree->left, smallTree);
    if (isLeftSubTree )
        return true;
    else
        return isSubtree(bigTree->right, smallTree);

}

Solution 2:

Use a suffix tree.
1. do a traversal { takes O(m) } for the larger tree and create a suffix tree.{ takes O(m) time + O(m) space }

2. do a traversal { takes O(n) } for the smaller tree and check if this pattern exists in the suffix tree. { O(n) time }