# Interview Questions

Ritambhara Technologies - Coding Interview Preparations > Interview Questions > Algorithms > Check if a Binary tree is sub-tree of another

# Check if a Binary tree is sub-tree of another

- June 11, 2012
- Posted by: Kamal Rawat
- Category: Algorithms

No Comments

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