# Check if a tree is a subtree of another tree?

195 views
Check if a tree is a subtree of another tree?
posted Nov 26, 2013

Basically You need two functions one for checking if both the tree are identical or not and second to check if it is subtree of another.
1. Step 1, if both tree are identical return true.
2. Return isSubTree(node->left, S) || isSubTree(node->right, S)
where S is second tree to be checked.

Sample Code

``````/* A utility function to check whether trees with roots as root1 and
root2 are identical or not */
bool areIdentical(struct node * root1, struct node *root2)
{
/* base cases */
if(root1 == NULL && root2 == NULL)
return true;

if(root1 == NULL || root2 == NULL)
return false;

/* Check if the data of both roots is same and data of left and right
subtrees are also same */
return (root1->data == root2->data   &&
areIdentical(root1->left, root2->left) &&
areIdentical(root1->right, root2->right) );
}

/* This function returns true if S is a subtree of T, otherwise false */
bool isSubtree(struct node *T, struct node *S)
{
/* base cases */
if (S == NULL)
return true;

if (T == NULL)
return false;

/* Check the tree with root as current node */
if (areIdentical(T, S))
return true;

/* If the tree with root as current node doesn't match then
try left and right subtrees one by one */
return isSubtree(T->left, S) ||
isSubtree(T->right, S);
}
``````
``````                    50                      50