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
int issubtree(const tree *haystack, const tree *needle)\$\endgroup\$