Code:
#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:
No: S is NOT a subtree of T
------------------
(program exited with code: 0)
Press return to continue
More C++ Programs:
