Binary Tree: Given two trees, check if the tree is subtree of another tree

Problem Statement:

Given two trees, check if the tree is subtree of another tree.

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

    /*

     *        12
     *       /  \
     *      11   14
     */

Output:

True

Solution Explanation:

We need to check if the tree “t” is a subtree of “s”.

Start comparing the first node of s and t.

if they match, then pass the left and right node and check if they are subtree.

Else, we will move to the next node and check again.

Continue till the end of the subtree.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

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

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


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_inorder(Node* root)
{
    if (root == NULL)
        return;

    display_inorder(root->left);
    cout << root->data << " ";
    display_inorder(root->right);
}


void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}



bool isSametree(Node* s, Node* t)
{
   // check if any of the tree is NULL
   if(!s || !t)
   {
       return s==NULL && t==NULL;
   } 
   else if(s->data == t->data)
   {
       return isSametree(s->left,t->left) && isSametree(s->right,t->right);
   }
   else
   {
       return false;
   }
}

bool solution(Node* s, Node* t) 
{
	 //if the main tree is NULL, then return false
     if(!s)
     {
         return false;
     }   
     else if(isSametree(s,t)) //start from root node of s
     {
         return true;
     }
     else
     {
         //else start with the left and right node of the source tree
         return solution(s->left,t) || solution(s->right,t);
     }
}

int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

    struct Node* root_1 = newNode(10);
    root_1->left = newNode(8);
    root_1->right = newNode(12);
    root_1->left->left = newNode(2);
    root_1->left->right = newNode(9);
    root_1->right->left = newNode(11);
    root_1->right->right = newNode(14);

    /*
     *        12
     *       /  \
     *      11   14
     */


    struct Node* root_2 = newNode(12);
    root_2->left = newNode(11);
    root_2->right = newNode(14);

    cout<<solution(root_1, root_2);
    return 0;
}

Output

1