Given the roots of two binary trees root and rootSub, check if there is a subtree of root with the same structure and node values as rootSub.
A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T.
Pseudocode
1. Traverse the given binary trees rooted at root and rootSub in a preorder fashion.
2. Do if root == NULL && rootSub == NULL,
return true
3. Else if either of the two is null not both,
ie root == NULL || rootSub == NULL,
return false
4. Traverse root->left && rootSub->left and
root->right && rootSub->right
5. If info[root->left] && info[root->right] for both root and rootSub
match equal,
return true
6. Else, return false
Code Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | //// main.cpp// Subtree//// Created by Himanshu on 15/09/21.////// main.cpp// Ancestors of a node//// Created by Himanshu on 15/09/21.//#include <iostream>#include <queue>using namespace std;struct node { int info = 0; struct node *left, *right;};typedef struct node Node;node* newNode(int data){ node* Node = new node(); Node->info = data; Node->left = NULL; Node->right = NULL; return(Node);}bool check(Node *root, Node *rootSub) { if (root == NULL && rootSub == NULL) { return true; } else if (root == NULL || rootSub == NULL) { return false; } if (root->info == rootSub->info && check(root->left, rootSub->left) && check(root->right, rootSub->right)) { return true; } else { return false; } }bool isSubtree (Node *root, Node *rootSub) { if (root == NULL) { return false; } else if (check(root, rootSub)) { return true; } else { return ((isSubtree(root->left, rootSub)) || (isSubtree(root->right, rootSub))); }}int main() { Node *root = newNode(1); root->left = newNode(20); root->right = newNode(21); root->right->left = newNode(30); root->right->right = newNode(31); root->right->right->left = newNode(40); root->right->right->left->right = newNode(51); Node *rootSub = newNode(21); rootSub->left = newNode(30); rootSub->right = newNode(31); rootSub->right->left = newNode(40); rootSub->right->left->right = newNode(51); Node *rootSub2 = newNode(21); rootSub2->left = newNode(30); rootSub2->right = newNode(31); rootSub2->right->left = newNode(40); rootSub2->right->left->right = newNode(50); cout<<"Is rootSub a subtree of root? "<<endl; cout<<isSubtree(root, rootSub); cout<<endl; cout<<"Is rootSub2 a subtree of root? "<<endl; cout<<isSubtree(root, rootSub2); cout<<endl; return 0;} |
Output:
Is rootSub a subtree of root? 1 Is rootSub2 a subtree of root? 0
Here’s a working example: Ideone
Time Complexity of above solution is O(m*n) where m and n are number of nodes in given two trees respectively.