The logic behind checking if a binary tree is a subtree in another binary tree (super tree) is
Examples of a binary tree being / not being a subtree in another binary tree
Time complexity of checking if a binary tree is a subtree in another tree : O(nm) where ‘n’ is the number of nodes in the super tree (i.e the tree that we are searching in) and ‘m’ is the number of node in the tree that is being searched for.
C++14 Finding a binary subtree in a super tree
#include<iostream>
#include<vector>
using namespace std;
class Node{
public:
Node(int n):data(n),left(NULL),right(NULL){
}
Node * left;
Node * right;
int data;
};
// Check if the 2 trees (subtree and super tree) are identical.
bool AreTreesIdentical(Node * root_super, Node * root_sub){
if(root_super == NULL && root_sub == NULL)
return true;
if(root_super == NULL || root_sub == NULL)
return false;
/* These recursive calls return true if the left and right subtrees
are identical and the nodes themselves are same in value */
return (AreTreesIdentical(root_super->left, root_sub->left) &&
AreTreesIdentical(root_super->right, root_sub->right) &&
(root_super->data == root_sub->data));
}
bool FindBinarySubtree(Node * root_super, Node * root_sub){
if(root_sub == NULL)
return true;
/* Super tree: The tree in which we are searching for a subtree.
If the super tree is empty the subtree definitely cannot be found */
if(root_super == NULL)
return false;
if(AreTreesIdentical(root_super, root_sub) == true)
return true;
// Check for the subtree in the left and right part of the super tree.
return ( FindBinarySubtree(root_super->left, root_sub) ||
FindBinarySubtree(root_super->right, root_sub) );
}
int main() {
/* Constructed binary tree is
9
/ \
5 16
/ \ / \
3 7 12 18
/ \ \
6 8 25
/ \
20 36
*/
Node *root = new Node(9);
root->left = new Node(5);
root->right = new Node(16);
root->left->left = new Node(3);
root->left->right = new Node(7);
root->left->right->left = new Node(6);
root->left->right->right = new Node(8);
root->right->left = new Node(12);
root->right->right = new Node(18);
root->right->right->right = new Node(25);
root->right->right->right->left = new Node(20);
root->right->right->right->right = new Node(36);
/* Subtree
18
\
25
/ \
20 36 */
Node *root1 = new Node(18);
root1->right = new Node(25);
root1->right->left = new Node(20);
root1->right->right = new Node(36);
/* Subtree
7
/ \
6 8
\
9 */
Node *root2 = new Node(7);
root2->right = new Node(8);
root2->left = new Node(6);
root2->right->right = new Node(9);
/* Subtree
16
\
18 */
Node *root3 = new Node(16);
root3->right = new Node(18);
/* Subtree
3 */
Node *root4 = new Node(3);
vector<Node*> vec_subtree_roots = { root1, root2, root3, root4 };
for(auto & subtree_root : vec_subtree_roots) {
if(FindBinarySubtree(root, subtree_root) == true){
cout << "Binary subtree with root " << subtree_root->data << " exist in binary tree with root " << root->data << endl;
} else {
cout << "Binary subtree with root " << subtree_root->data << " does not exist in binary tree with root " << root->data << endl;
}
}
return 0;
}
Output
Binary subtree with root 18 exist in binary tree with root 9
Binary subtree with root 7 does not exist in binary tree with root 9
Binary subtree with root 16 does not exist in binary tree with root 9
Binary subtree with root 3 exist in binary tree with root 9