Invert traingle made from 6 circles
June 11, 2012
Effect on area of rt angled triangle if base is increased and hight reduced
June 11, 2012

Check if a Binary tree is sub-tree of another

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

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