Algotree > Algorithms > Tree & Graph Traversal > Check If A binary tree is a subtree in another binary tree (super tree)

Check If A binary tree is a subtree in another binary tree (super tree)

Check if a binary tree is a subtree in another binary tree (super tree)

The logic behind checking if a binary tree is a subtree in another binary tree (super tree) is

The super tree that we are searching in shouldn’t be empty/null.
Every node in the searched tree and its children and their children, are present in the super tree at the same positions. This search is done recursively.

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 and root_sub == NULL)
       return true;

    if(root_super == NULL or root_sub == NULL)
       return false;

    return (AreTreesIdentical(root_super->left, root_sub->left) and
            AreTreesIdentical(root_super->right, root_sub->right) and
            (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;

    return ( FindBinarySubtree(root_super->left, root_sub) or
             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