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-&gt;data == tree2p-&gt;data)
        return (issubtree(tree1p-&gt;leftp,tree2p-&gt;leftp) 
                &amp;&amp; (issubtree(tree1p-&gt;leftp,tree2p-&gt;leftp));
    else
        return (issubtree(tree1p-&gt;leftp,tree2p) || (issubtree(tree1p-&gt;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-&gt;data != tree2-&gt;data) return 0;
    return matches(tree1-&gt;left, tree2-&gt;left) &amp;&amp; matches(tree1-&gt;right, tree2-&gt;right);
}

int issubtree(tree *haystack, tree * needle)
{
    if(tree1 == haystack) return 0;
    if( matches(haystack, needle) ) return 1;
    return issubtree(haystack-&gt;left, tree2) || issubtree(haystack-&gt;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