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
//
// 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.