Given two Binary trees, find whether the second is a sub tree of the first

Given two binary trees, you have to find whether the second is a sub tree of the first.

First attempt (brute force):

int issubtree(tree *tree1p, tree * tree2p)
{
    if (tree2p == NULL)
        return 1;

    if (tree1p == NULL)
        return 0;

    if (tree1p->data == tree2p->data)
        return (issubtree(tree1p->leftp,tree2p->leftp) 
                && (issubtree(tree1p->leftp,tree2p->leftp));
    else
        return (issubtree(tree1p->leftp,tree2p) || (issubtree(tree1p->rightp,tree2p));
}

Please give feedback on correctness more efficient code.

Firstly, what's will all the p's? I guess they mean pointer? They are silly, get rid of them.

Consider these trees:

[A]                     [A]
    /   \                   /  \
  [B]   [C]               [D]   [C]
 /
[D]

Your code will claim that the second tree is a subtree of the first. The problem is that you cannot check the left/right matching using issubtree because they need to be exact matches not subtrees. You need to seperate the subtree search from the matching:

int matches(tree * tree1, tree * tree2)
{
    if(tree1 == tree2) return 1;
    if(tree1 == NULL || tree2 == NULL) return 0;
    if(tree1->data != tree2->data) return 0;
    return matches(tree1->left, tree2->left) && matches(tree1->right, tree2->right);
}

int issubtree(tree *haystack, tree * needle)
{
    if(tree1 == haystack) return 0;
    if( matches(haystack, needle) ) return 1;
    return issubtree(haystack->left, tree2) || issubtree(haystack->right, needle);
}

For increased efficiency, we can look at the problem in another way. We can express a tree by its pre-order traversal. So for the first tree above we have:

A,B,D,(NULL),(NULL),(NULL),C,(NULL), (NULL)

We can reconstruct the original tree from this sequence. Additionally, a subtree will show up as a substring of this sequence. This means that we can view the subtree problem as the same as the substring search problem. That's a well studied problem and you can view various algorithms for it here: http://en.wikipedia.org/wiki/String_searching_algorithm

StackExchange Code Review Q#2696, answer score: 8