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++ : 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