Check if a binary tree is a subtree of another binary tree

You are given the root nodes of two trees T and S, you need to check whether S is a subtree of T or not. A tree S is a subtree of a tree T if S consists of a node in T and all of its descendants.

Consider the example below.

Tree T
              26
            /   \
          10     3
        /    \     \
      4       6      3
       \
        30
Tree S
          10  
        /    \ 
      4       6
       \
        30

In the above example, Tree S is a subtree of Tree T.

Algorithm

  1. To solve the above problem, we create a utility function called areIdentical. In this method, we take as argument two root nodes. It checks whether the trees with two given roots are identical or not. If Root1 and Root2 are both null, we return true. If any one of them is null, we return false. Else, if both the root’s data are equal and recursive call on left and right subtrees are also true, we return true.
  2. We create another function isSubTree which takes as arguments the roots of the two trees (Say T and S, where T is the root of the parent tree and S is the root of the subtree). If root of subtree is null, we return true. If root of parent tree is null and subtree’s root is not null, we return false. If trees rooted at T and S are identical (checking using the utility function), we return true.
    Else, we return ( isSubTree(T->left, S) || isSubTree(T->right, S) ).

Take a look at the code for better understanding.

#include <bits/stdc++.h>

using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root1 = nullptr;
Node* root2 = nullptr;

void levelOrderTraversal(Node* root){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}

bool areIdentical(Node * root1, Node *root2)  
{  
    /* base cases */
    if (root1 == nullptr && root2 == nullptr){
        return true;
    } 
  
    if (root1 == nullptr || root2 == nullptr){
        return false;
    }  
  
    /* Check if the data of both roots is same and data of left and right  
    subtrees are also same */
    return (root1->data == root2->data && areIdentical(root1->left, root2->left) && areIdentical(root1->right, root2->right));  
}  
  

bool isSubtree(Node *T, Node *S)  
{  
    /* base cases */
    if (S == nullptr){
        return true; 
    }  
         
    if (T == nullptr){
        return false; 
    }  
         
    /* Check the tree with root as current node */
    if (areIdentical(T, S)){
        return true;
    }  
  
    /* If the tree with root as current node doesn't match then try left  
    and right subtrees one by one */
    return isSubtree(T->left, S) ||  isSubtree(T->right, S);  
}

int main()
{
    root1 = createNode(8);
    root1->left = createNode(3);
    root1->right = createNode(10);
    root1->left->left = createNode(1);
    root1->left->right = createNode(6);
    root1->left->right->left = createNode(4);
    root1->left->right->right = createNode(7);
    root1->right = createNode(10);
    root1->right->right = createNode(14);
    root1->right->right->left = createNode(13);

    root2 = createNode(3);
    root2->left = createNode(1);
    root2->right = createNode(6);
    root2->right->left = createNode(4);
    root2->right->right = createNode(7);


    cout<<"Level order traversal of parent tree => ";
    levelOrderTraversal(root1);
    cout<<endl;
    cout<<"Level order traversal of subtree => ";
    levelOrderTraversal(root2);
    cout<<endl<<endl;
    if(isSubtree(root1, root2)){
        cout<<"It is a subtree";
    }else{
        cout<<"It is not a subtree";
    }
    return 0;
}

Also, take a look at another popular interview problem Construct a BST from preorder traversal.

Leave a Reply

Your email address will not be published.