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.

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. #define MAX 100
  5.  
  6. // Structure of a tree node
  7. struct Node
  8. {
  9.         char key;
  10.         struct Node *left, *right;
  11. };
  12.  
  13. // A utility function to create a new BST node
  14. Node *newNode(char item)
  15. {
  16.     Node *temp = new Node;
  17.     temp->key = item;
  18.     temp->left = temp->right = NULL;
  19.     return temp;
  20. }
  21.  
  22. // A utility function to store inorder traversal of tree rooted
  23. // with root in an array arr[]. Note that i is passed as reference
  24. void storeInorder(Node *root, char arr[], int &i)
  25. {
  26.     if (root == NULL)
  27.     {
  28.         arr[i++] = '$';
  29.         return;
  30.     }
  31.     storeInorder(root->left, arr, i);
  32.     arr[i++] = root->key;
  33.     storeInorder(root->right, arr, i);
  34. }
  35.  
  36. // A utility function to store preorder traversal of tree rooted
  37. // with root in an array arr[]. Note that i is passed as reference
  38. void storePreOrder(Node *root, char arr[], int &i)
  39. {
  40.     if (root == NULL)
  41.     {
  42.         arr[i++] = '$';
  43.         return;
  44.     }
  45.     arr[i++] = root->key;
  46.     storePreOrder(root->left, arr, i);
  47.     storePreOrder(root->right, arr, i);
  48. }
  49.  
  50. /* This function returns true if S is a subtree of T, otherwise false */
  51. bool isSubtree(Node *T, Node *S)
  52. {
  53.     /* base cases */
  54.     if (S == NULL)
  55.         return true;
  56.     if (T == NULL)
  57.         return false;
  58.  
  59.     // Store Inorder traversals of T and S in inT[0..m-1]
  60.     // and inS[0..n-1] respectively
  61.     int m = 0, n = 0;
  62.     char inT[MAX], inS[MAX];
  63.     storeInorder(T, inT, m);
  64.     storeInorder(S, inS, n);
  65.     inT[m] = '\0', inS[n] = '\0';
  66.  
  67.     // If inS[] is not a substring of preS[], return false
  68.     if (strstr(inT, inS) == NULL)
  69.         return false;
  70.  
  71.     // Store Preorder traversals of T and S in inT[0..m-1]
  72.     // and inS[0..n-1] respectively
  73.     m = 0, n = 0;
  74.     char preT[MAX], preS[MAX];
  75.     storePreOrder(T, preT, m);
  76.     storePreOrder(S, preS, n);
  77.     preT[m] = '\0', preS[n] = '\0';
  78.  
  79.     // If inS[] is not a substring of preS[], return false
  80.     // Else return true
  81.     return (strstr(preT, preS) != NULL);
  82. }
  83.  
  84. // Driver program to test above function
  85. int main()
  86. {
  87.     Node *T = newNode('a');
  88.     T->left = newNode('b');
  89.     T->right = newNode('d');
  90.     T->left->left = newNode('c');
  91.     T->right->right = newNode('e');
  92.  
  93.     Node *S = newNode('a');
  94.     S->left = newNode('b');
  95.     S->left->left = newNode('c');
  96.     S->right = newNode('d');
  97.  
  98.     if (isSubtree(T, S))
  99.         cout << "Yes: S is a subtree of T";
  100.     else
  101.         cout << "No: S is NOT a subtree of T";
  102.  
  103.     return 0;
  104. }

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.

advertisement
advertisement

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

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.