# How to find if a Tree is a subtree of the given tree in C++

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
3.   Traverse root->left && root->right and
rootSub->left && rootSub->right
4.   If info[root->left] && info[root->right] for both root and rootSub match equal, return true
5.   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:

https://ideone.com/qcm6D2

Time Complexity of above solution is O(m*n) where m and n are number of nodes in given two trees respectively.