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);
}

One Thought 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!!

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