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

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

Finding_Binary_Subtree

The idea behind checking if a given binary tree is a subtree in another binary tree (supertree) is

The supertree that we are searching in shouldn’t be empty / null.
The structure of a given tree i.e the root, root’s left sub-tree, and root’s right-subtree are the same in the supertree.
The left node of the given tree should be a leaf node in the supertree.
Example : Consider tree D with root ( 16 ) and right child ( 18 ).
Even though we see the same structure in the supertree, but tree D is not a subtree in the supertree as its leaf node 18 is not a leaf node in the supertree.

Thus we see,
Tree A is present as a subtree in the supertree.
Tree B is not present as a subtree in the supertree.
Tree C is present as a subtree in the supertree.
Tree D is not present as a subtree in the supertree.

Time complexity : O ( n m ) where ‘n’ is the number of nodes in the supertree (i.e the tree that we are searching in) and ’m' is the number of nodes in the tree being searched for.

C++ : Finding a binary subtree in a super tree

#include<iostream>
#include<vector>
using namespace std;

class Node {

    public:
    int data;
    Node * left;
    Node * right;
    Node(int x, Node * left_node = nullptr, Node * right_node = nullptr) : data(x), left(left_node), right(right_node)
    {}
};

// 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 have same data*/
    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 node3(3), node6(6), node8(8), node12(12), node20(20), node36(36);
    Node node7(7, &node6, &node8);
    Node node25(25, &node20, &node36);
    Node node18(18, nullptr, &node25);
    Node node16(16, &node12, &node18);
    Node node5(5, &node3, &node7);
    Node root_node9(9, &node5, &node16);

    /* Subtree
         18
          \
          25
         /  \
        20  36  */

    Node _node20(20), _node36(36);
    Node _node25(25, &_node20, &_node36);
    Node root_node18(18, nullptr, &node25);

    /* Subtree
         7
        / \
       6   8
            \
             9 */

    Node _node9(9), _node6(6);
    Node _node8(8, nullptr, &_node9);
    Node root_node7(7, &_node6, &_node8);

    /* Subtree
        16
         \
          18 */
    Node _node18(18);
    Node root_node16(16, nullptr, &_node18);

    /* Subtree
        3 */

    Node root_node3(3);

    vector<Node> subtree_roots = { root_node18, root_node7, root_node16, root_node3 };

    for(auto & subtree_root : subtree_roots) {
        if(FindBinarySubtree(&root_node9, &subtree_root) == true){
           cout << "Binary subtree with root " << subtree_root.data << " exist in binary tree with root " << root_node9.data << endl;
        } else {
           cout << "Binary subtree with root " << subtree_root.data << " does not exist in binary tree with root " << root_node9.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