C++ Program to Check if Binary Tree is Subtree of Another Tree

This is a C++ Program to check whether 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 <iostream>
```
```
#include <cstring>
```
```
using namespace std;
```
```
#define MAX 100
```
```
 
```
```
// Structure of a tree node
```
```
struct Node
```
```
{
```
```
        char key;
```
```
        struct Node *left, *right;
```
```
};
```
```
 
```

// A utility function to create a new BST node

```
Node *newNode(char item)
```
```
{
```
```
    Node *temp = new Node;
```
```
    temp->key = item;
```
```
    temp->left = temp->right = NULL;
```
```
    return temp;
```
```
}
```
```
 
```

// A utility function to store inorder traversal of tree rooted

// with root in an array arr[]. Note that i is passed as reference

void storeInorder(Node *root, char arr[], int &i)

```
{
```
```
    if (root == NULL)
```
```
    {
```
```
        arr[i++] = '$';
```
```
        return;
```
```
    }
```
```
    storeInorder(root->left, arr, i);
```
```
    arr[i++] = root->key;
```
```
    storeInorder(root->right, arr, i);
```
```
}
```
```
 
```

// A utility function to store preorder traversal of tree rooted

// with root in an array arr[]. Note that i is passed as reference

void storePreOrder(Node *root, char arr[], int &i)

```
{
```
```
    if (root == NULL)
```
```
    {
```
```
        arr[i++] = '$';
```
```
        return;
```
```
    }
```
```
    arr[i++] = root->key;
```
```
    storePreOrder(root->left, arr, i);
```
```
    storePreOrder(root->right, arr, i);
```
```
}
```
```
 
```

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

```
bool isSubtree(Node *T, Node *S)
```
```
{
```
```
    /* base cases */
```
```
    if (S == NULL)
```
```
        return true;
```
```
    if (T == NULL)
```
```
        return false;
```
```
 
```

    // Store Inorder traversals of T and S in inT[0..m-1]

```
    // and inS[0..n-1] respectively
```
```
    int m = 0, n = 0;
```
```
    char inT[MAX], inS[MAX];
```
```
    storeInorder(T, inT, m);
```
```
    storeInorder(S, inS, n);
```
```
    inT[m] = '\0', inS[n] = '\0';
```
```
 
```

    // If inS[] is not a substring of preS[], return false

```
    if (strstr(inT, inS) == NULL)
```
```
        return false;
```
```
 
```

    // Store Preorder traversals of T and S in inT[0..m-1]

```
    // and inS[0..n-1] respectively
```
```
    m = 0, n = 0;
```
```
    char preT[MAX], preS[MAX];
```
```
    storePreOrder(T, preT, m);
```
```
    storePreOrder(S, preS, n);
```
```
    preT[m] = '\0', preS[n] = '\0';
```
```
 
```

    // If inS[] is not a substring of preS[], return false

```
    // Else return true
```

    return (strstr(preT, preS) != NULL);

```
}
```
```
 
```

// Driver program to test above function

```
int main()
```
```
{
```
```
    Node *T = newNode('a');
```
```
    T->left = newNode('b');
```
```
    T->right = newNode('d');
```
```
    T->left->left = newNode('c');
```
```
    T->right->right = newNode('e');
```
```
 
```
```
    Node *S = newNode('a');
```
```
    S->left = newNode('b');
```
```
    S->left->left = newNode('c');
```
```
    S->right = newNode('d');
```
```
 
```
```
    if (isSubtree(T, S))
```

        cout << "Yes: S is a subtree of T";

```
    else
```

        cout << "No: S is NOT a subtree of T";

```
 
```
```
    return 0;
```
```
}
```

Output:

$ g++ CheckForBinarySubtree.cpp
$ a.out
 
No: S is NOT a subtree of T
 
------------------
(program exited with code: 0)
Press return to continue

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

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

« Prev - C++ Program to Create Mirror Image of a Binary Tree

» Next - C++ Program to Remove All nodes which don’t lie in Any Path with Sum >= K

Related Posts:

Recommended Articles: