How to find if a Tree is a subtree of the given tree in C++

Given the roots of two binary trees root and rootSub,  check if there is a subtree of root with the same structure and node values as rootSub

A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T.

Pseudocode

1. Traverse the given binary trees rooted at root and rootSub in a preorder fashion.
2. Do if root == NULL && rootSub == NULL, return true
3. Else if either of the two is null not both, 
     ie root == NULL || rootSub == NULL, return false
3.   Traverse root->left && root->right and 
     rootSub->left && rootSub->right
4.   If info[root->left] && info[root->right] for both root and rootSub match equal, return true
5.   Else, return false 

Code Implementation

//
//  main.cpp
//  Subtree
//
//  Created by Himanshu on 15/09/21.
//

//
//  main.cpp
//  Ancestors of a node
//
//  Created by Himanshu on 15/09/21.
//

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

struct node {
    int info = 0;
    struct node *left, *right;
};
typedef struct node Node;

node* newNode(int data)
{
    node* Node = new node();
    Node->info = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return(Node);
}

bool check(Node *root, Node *rootSub) {
    if (root == NULL && rootSub == NULL) {
        return true;
    } else if (root == NULL || rootSub == NULL) {
        return false;
    }
    if (root->info == rootSub->info && check(root->left, rootSub->left) &&
        check(root->right, rootSub->right)) {
        return true;
    } else {
        return false;
    }
        
}

bool isSubtree (Node *root, Node *rootSub) {
    if (root == NULL) {
        return false;
    } else if (check(root, rootSub)) {
        return true;
    } else {
        return ((isSubtree(root->left, rootSub)) || (isSubtree(root->right, rootSub)));
    }
}


int main() {
    Node *root = newNode(1);
    root->left = newNode(20);
    root->right = newNode(21);
    root->right->left = newNode(30);
    root->right->right = newNode(31);
    root->right->right->left = newNode(40);
    root->right->right->left->right = newNode(51);
    
    Node *rootSub = newNode(21);
    rootSub->left = newNode(30);
    rootSub->right = newNode(31);
    rootSub->right->left = newNode(40);
    rootSub->right->left->right = newNode(51);
    
    Node *rootSub2 = newNode(21);
    rootSub2->left = newNode(30);
    rootSub2->right = newNode(31);
    rootSub2->right->left = newNode(40);
    rootSub2->right->left->right = newNode(50);

    cout<<"Is rootSub a subtree of root? "<<endl;
    cout<<isSubtree(root, rootSub);
    cout<<endl;
    
    cout<<"Is rootSub2 a subtree of root? "<<endl;
    cout<<isSubtree(root, rootSub2);
    cout<<endl;

    return 0;
}

Output:

Is rootSub a subtree of root? 
1
Is rootSub2 a subtree of root? 
0

Here’s a working example:

https://ideone.com/qcm6D2

Time Complexity of above solution is O(m*n) where m and n are number of nodes in given two trees respectively. 

Leave a Reply

Your email address will not be published.