Check if a Binary tree is sub-tree of another

Given pointers to the root of two Binary Trees, write code to check if the first Binary tree is a subtree of the second binary tree. The signature (prototype) of the function in C++ should be
/** returns 1 (true) if Binary Tree a is subtree of Binary tree b ,
 *  else returns 0(false)
 */
int checkSubTree(Node* r1, Node* r2);
Note that the subtree should be present in structure and value in the tree. For example, the below tree
    10
   /  \
  4    6
 /
30
is a subtree of
       25
      /   \
     10     7
    / \    / \
    4 6  2  9
   /
  30

Solution:

Traverse the second binary tree (r2) in in-order traversal. For each node (of the second tree), check if the subtree rooted at this node is same as our first Binary Tree (r1)
/** returns 1 (true) if Binary Tree r1 is subtree of Binary tree r2 , else returns 0(false)
 */
 int checkSubTree(node *r1, node *r2)
 {
     if (a == NULL)
         return 1; // TRUE
     if (b == NULL)
         return 0; // FALSE
     // Check if current subtree is same as a.
     if (areEqual(r1, r2))
         return 1;
     // Try left and right subtrees one by one
    return isSubtree(r1, r2->left) ||
          isSubtree(r1, r2->right);
 }
 /* Recursive Function to check if the two trees are identical or not */
 int areEqual(struct Node * a, struct Node *b)
 {
    if(a == NULL)
         return 1;
    // If one of them is NULL but other has some value
    // Because we are checking exact equality
     if(b == NULL)
         return 0;
     return (a->data == b->data &&
             areEqual(a->left, b->left) &&
             areEqual(a->right, b->right) );
 }

0 Comments

Leave a comment