# 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.

• I'd come up with better (subjective, I know) names for the parameters: int issubtree(const tree *haystack, const tree *needle)
– pmg
May 29, 2011 at 14:56
• Why cant we get the list of preorder and inorder of both the trees and compare the preorder and inorder of 2 is a subseq of preorder and inorder of 1
– user6794
Aug 31, 2011 at 16:57

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

• When looking at the wikipedia example for pre-order en.wikipedia.org/wiki/Tree_traversal#Pre-order you can not match sub-tree F,A,B,D,G as substring because C and E are in between.
– Flip
Dec 2, 2013 at 21:12
• @Flip, that's not a subtree. From wiki: "A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T" C & E have to be included for it to be a subtree. Dec 3, 2013 at 3:24
• I tested mentioned code with your example, but it gives me correct answer. Am I missing something? Code: ideone.com/GLt7za Aug 24, 2015 at 13:37
• @Hengameh, you inputted the tree incorrectly, you swapped left and right in the first tree. Aug 24, 2015 at 14:07
• You are right! Embarrassing! Sorry. Aug 24, 2015 at 14:35

This algorithm requires the values to maintain the same structure in both trees which is probably okay for this assignment (homework?).

If these are binary search trees, there's at least one optimization you can make right off the bat: inside the else block you don't have to check both directions. Think about how you would find the root node of the subtree in the main tree.

And yes, choosing meaningful variable and function names and using consistent formatting (I fixed it) goes a long way toward keeping code readable.