This is a C Program program to check whether a binary tree is subtree of another tree. Given two binary trees, check if the first tree is subtree of the second one. A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.

Here is source code of the C Program to Check Whether an Input Binary Tree is the Sub Tree of the Binary Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`#include <stdio.h>`

`#include <stdlib.h>`

`/* A binary tree node has data, left child and right child */`

struct node {

int data;

struct node* left;

struct node* right;

};

`/* A utility function to check whether trees with roots as root1 and`

`root2 are identical or not */`

bool areIdentical(struct node * root1, struct node *root2) {

`/* base cases */`

if (root1 == NULL && root2 == NULL)

return true;

if (root1 == NULL || root2 == NULL)

return false;

`/* Check if the data of both roots is same and data of left and right`

`subtrees are also same */`

return (root1->data == root2->data

&& areIdentical(root1->left, root2->left) && areIdentical(

root1->right, root2->right));

`}`

`/* This function returns true if S is a subtree of T, otherwise false */`

bool isSubtree(struct node *T, struct node *S) {

`/* base cases */`

if (S == NULL)

return true;

if (T == NULL)

return false;

`/* Check the tree with root as current node */`

if (areIdentical(T, S))

return true;

`/* If the tree with root as current node doesn't match then`

`try left and right subtrees one by one */`

return isSubtree(T->left, S) || isSubtree(T->right, S);

`}`

`/* Helper function that allocates a new node with the given data`

`and NULL left and right pointers. */`

struct node* newNode(int data) {

struct node* node = (struct node*) malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return (node);

`}`

`/* Driver program to test above function */`

int main() {

`/* Construct the following tree`

`26`

`/ \`

`10 3`

`/ \ \`

`4 6 3`

`\`

`30`

`*/`

struct node *T = newNode(26);

T->right = newNode(3);

T->right->right = newNode(3);

T->left = newNode(10);

T->left->left = newNode(4);

T->left->left->right = newNode(30);

T->left->right = newNode(6);

`/* Construct the following tree`

`10`

`/ \`

`4 6`

`\`

`30`

`*/`

struct node *S = newNode(10);

S->right = newNode(6);

S->left = newNode(4);

S->left->right = newNode(30);

if (isSubtree(T, S))

printf("Tree S is subtree of tree T");

`else`

printf("Tree S is not a subtree of tree T");

getchar();

return 0;

`}`

Output:

$ gcc SubTree.c $ ./a.out Tree S is subtree of tree T

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

advertisement

advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

**Next Steps:**

- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

**Related Posts:**

- Apply for Computer Science Internship
- Buy Data Structure Books
- Practice Computer Science MCQs
- Buy Programming Books
- Practice Design & Analysis of Algorithms MCQ