- Write a C program to check if one binary tree is subtree of another binary tree using recursion.

Given two binary tree, we have to check **whether one binary tree is subtree of another binary tree**. A binary tree T is said to be the sub tree of another binary tree T2, if a tree rooted at any of the nodes of T2 is identical to T1. We will traverse every node of T2 and compare T1 with the sub tree rooted at every node of T2.

**Two trees are identical**if, both contains same set of nodes and the relative arrangement of nodes in both trees are also same.

**Algorithm to check if one binary tree is subtree of another binary tree**

Let "root1" and "root2" be the root nodes of two binary tree T1 and T2 respectively. We want to check whether T2 is subtree of T1 or not.

- If root2 is equal to NULL, then return true because an empty tree is sub tree of all binary tree.
- If root1 is equal to NULL, then return false.
- Check if the subtree rooted at root1 is identical to T2, If yes then return true.
- Else, recursively check whether T2 is sub tree of left or right subtree of root1.

**Time Complexity**: O(mn), where m and n are the number of nodes in both trees.

## C program to check whether one binary tree is subtree of another binary tree

#include <stdio.h> #define TRUE 1 #define FALSE 0 struct node { int data; struct node *left; struct node *right; }; struct node* getNewNode(int data) { /* dynamically allocate memory for a new node */ struct node* newNode = (struct node*)malloc(sizeof(struct node)); /* populate data in new Node */ newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } /* This function returns below tree 1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9 */ struct node* generateBTree(){ // Root Node struct node* root = getNewNode(1); root->left = getNewNode(2); root->right = getNewNode(3); root->left->left = getNewNode(4); root->left->right = getNewNode(5); root->right->left = getNewNode(6); root->right->right = getNewNode(7); root->left->left->left = getNewNode(8); root->left->left->right = getNewNode(9); return root; } /* Checks, if two trees are same or not */ int isIdentical(struct node *first, struct node *second){ /*If both are NULL , then Identical */ if(first == NULL && second == NULL) return TRUE; /* If only one tree is NULL, then not Identical */ if(first == NULL || second == NULL) return FALSE; /* IF left sub-trees, right subtrees and root node of both trees are same then both trees are identical */ if(isIdentical(first->left, second->left) && isIdentical(first->right, second->right) && first->data == second->data){ return TRUE; } else { return FALSE; } } /* This function check whether second is a subtree of first or not. */ int checkSubTree(struct node *first, struct node *second) { /* Recursion termination condition */ if (second == NULL) return TRUE; if(first == NULL) return FALSE; /* Check if tree with first as root is same as tree with second as root node */ if(isIdentical(first, second)){ return TRUE; } /* Recursively check, If left and right subtree of first is same as second*/ return checkSubTree(first->left, second) || checkSubTree(first->right, second); } int main() { struct node *root = generateBTree(); struct node *subtree = root->left; /* Printing ancestor's of nodes */ if(checkSubTree(root, subtree)){ printf("TRUE\n"); } else { printf("FALSE\n"); } getchar(); return 0; }Output

TRUE