top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

Check if a tree is a subtree of another tree?

+7 votes
186 views
Check if a tree is a subtree of another tree?
posted Nov 26, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button

1 Answer

0 votes

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);
}
answer Nov 26, 2013 by Meenal Mishra
Similar Questions
+6 votes
                    50                      50
                   /  \                    /  \
                  20     30              30   20
Sample Tree<---   /  \                       /  \   ----> Mirror image
               70      80                   80   70
              /  \    \                    /    /  \  
             10  40     60                60   40   10
+7 votes

Print cousins of a given node (Not sibling) ??

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...