fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Subtree
  4. //
  5. //  Created by Himanshu on 15/09/21.
  6. //
  7.  
  8. //
  9. //  main.cpp
  10. //  Ancestors of a node
  11. //
  12. //  Created by Himanshu on 15/09/21.
  13. //
  14.  
  15. #include <iostream>
  16. #include <queue>
  17. using namespace std;
  18.  
  19. struct node {
  20.     int info = 0;
  21.     struct node *left, *right;
  22. };
  23. typedef struct node Node;
  24.  
  25. node* newNode(int data)
  26. {
  27.     node* Node = new node();
  28.     Node->info = data;
  29.     Node->left = NULL;
  30.     Node->right = NULL;
  31.  
  32.     return(Node);
  33. }
  34.  
  35. bool check(Node *root, Node *rootSub) {
  36.     if (root == NULL && rootSub == NULL) {
  37.         return true;
  38.     } else if (root == NULL || rootSub == NULL) {
  39.         return false;
  40.     }
  41.     if (root->info == rootSub->info && check(root->left, rootSub->left) &&
  42.         check(root->right, rootSub->right)) {
  43.         return true;
  44.     } else {
  45.         return false;
  46.     }
  47.  
  48. }
  49.  
  50. bool isSubtree (Node *root, Node *rootSub) {
  51.     if (root == NULL) {
  52.         return false;
  53.     } else if (check(root, rootSub)) {
  54.         return true;
  55.     } else {
  56.         return ((isSubtree(root->left, rootSub)) || (isSubtree(root->right, rootSub)));
  57.     }
  58. }
  59.  
  60.  
  61. int main() {
  62.     Node *root = newNode(1);
  63.     root->left = newNode(20);
  64.     root->right = newNode(21);
  65.     root->right->left = newNode(30);
  66.     root->right->right = newNode(31);
  67.     root->right->right->left = newNode(40);
  68.     root->right->right->left->right = newNode(51);
  69.  
  70.     Node *rootSub = newNode(21);
  71.     rootSub->left = newNode(30);
  72.     rootSub->right = newNode(31);
  73.     rootSub->right->left = newNode(40);
  74.     rootSub->right->left->right = newNode(51);
  75.  
  76.     Node *rootSub2 = newNode(21);
  77.     rootSub2->left = newNode(30);
  78.     rootSub2->right = newNode(31);
  79.     rootSub2->right->left = newNode(40);
  80.     rootSub2->right->left->right = newNode(50);
  81.  
  82.     cout<<"Is rootSub a subtree of root? "<<endl;
  83.     cout<<isSubtree(root, rootSub);
  84.     cout<<endl;
  85.  
  86.     cout<<"Is rootSub2 a subtree of root? "<<endl;
  87.     cout<<isSubtree(root, rootSub2);
  88.     cout<<endl;
  89.  
  90.     return 0;
  91. }
  92.  
  93.  
Success #stdin #stdout 0s 5540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Is rootSub a subtree of root? 
1
Is rootSub2 a subtree of root? 
0
https://ideone.com/qcm6D2
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!