Jun 112012
 

Given pointers to the root of two Binary Trees, write code to check if first Binary tree is subtree of second binary tree. The signature (prototype) of the function should be

/** returns 1 (true) if Binary Tree a is subtree of Binary tree b ,
 *  else returns 0(false)
 */
int checkSubTree(struct Node* a, struct Node* b);

For example: the below tree

    10
   /  \
  4    6
 /
30

is subtree of

       25
      /   \
     10     7
    / \    / \
    4 6  2  9
   /
  30

Solution:

Traverse the second binary tree (b) in in-order fashion. For each node, check if the subtree rooted at this node is identical (exactly same) as our first Binary Tree (a).

/** returns 1 (true) if Binary Tree a is subtree of Binary tree b , else returns 0(false)
 */
 int checkSubTree(struct node *a, struct node *b)
 {
     if (a == NULL)
         return 1;

     if (b == NULL)
         return 0;

     // Check if current subtree is same as a.
     if (areEqual(a, b))
         return 1;

     // Try left and right subtrees one by one
    return isSubtree(a, b->left) ||
          isSubtree(a, b->right);
 }

 /* Function to check if the two trees are identical or not */
 int areEqual(struct Node * a, struct Node *b)
 {
    // If both are empty
     if(a == NULL && b == NULL)
         return 1;

     // If one of them is NULL but other has some value
    // Because we are checking exact equality
     if(a == NULL || b == NULL)
         return 0;

     return (a->data == b->data &&
             areEqual(a->left, b->left) &&
             areEqual(a->right, b->right) );
 }

 Leave a Reply

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=""> <s> <strike> <strong>

(required)

(required)