Check if a binary tree is subtree of another tree

Given two binary trees T1 and T2, Find whether T2 is a subtree of T1.T1 has millions of nodes and T2 has hundreds of nodes.

Solution:
Traverse T1 in pre-order fashion. For each node, check if the subtree rooted at this node is identical (exactly same) as T2.

struct node
{
    int data;
    struct node* left;
    struct node* right;
};
bool identical(struct node * root1, struct node *root2)
{
    if(root1 == NULL && root2 == NULL)
        return true;

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

    return (root1->data == root2->data   &&
            identical(root1->left, root2->left) &&
            identical(root1->right, root2->right) );
}

bool checkSubtree(struct node *T1, struct node *T2)
{
    if (T2 == NULL)
        return true;

    if (T1 == NULL)
        return false;

    if (identical(T1, T2))
        return true;

    return checkSubtree(T1->left, T2) ||
           checkSubtree(T1->right, T2);
}

2 Thoughts on “Check if a binary tree is subtree of another tree

  1. Good blog you’ve got here.. It’s hard to find high-quality writing like yours these days.

    I truly appreciate people like you! Take care!!

  2. This doesn’t seem correct. Since, the tree T1 has million nodes, its prudent to search the root of T2 in T1 first rather than going for preorder (or any for that matter) traversal of T1. Once, you have the searched node in T1; run the algorithm to compare equal trees structurally on T1 and this searched node in T2. When T2 is done, stop in case program didn’t stop earlier. This would be the case of a success.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation