#include <iostream>

using namespace std;
template<class T>
class BSTNode
{
public:
    T key;
    BSTNode* right;
    BSTNode* left;
public:
    BSTNode()
    {
        right = NULL;
        left = NULL;
    }
    BSTNode(T DATA, BSTNode* right = 0 , BSTNode* left = 0)
    {
        key = DATA;
        this->right = right;
        this->left = left;
    }
    BSTNode*getleft(){return left;}
    BSTNode*getright(){return right;}
    T getkey(){return key;}
};
template<class T>
class BSTFCI
{
public:
    BSTNode<T>* root;
public:
    BSTFCI(){root = NULL;}
    BSTFCI(T data)
    {
        root->key = data;
        root->left = root->right = NULL;
    }

     //Recursion Function - Inserting new node to the binary search tree.
    BSTNode<T>* Insert_Node( T DATA,BSTNode<T>* node)
    {
        //InCase there is no node create root node.
        if(node == NULL)
        {
            node = new BSTNode<T>;
            node->key = DATA;
            node->left = node->right = NULL;
        }

        //InCase given key > node key -- > Go right subtree.
        else if( DATA > node->key )
            node->right = Insert_Node(DATA,node->right ); //Calling it self.

        //InCase given key < node key -- > Go left subtree.
        else if( DATA < node->key )
            node->left = Insert_Node(DATA,node->left );

        return node;

    }

    void Insert(T DATA)
    {
        root = Insert_Node(DATA, root);
    }
//Printing nodes left then root then right.
    void PrintTreeInOrder(BSTNode<T> * node)
    {
        if(node != NULL)
        {
            PrintTreeInOrder(node->left);
            cout << node->key<<" ";
            PrintTreeInOrder(node->right);
        }
    }
    void PrintTreeInOrder()
    {
        PrintTreeInOrder(root);
        cout <<endl;
    }

    friend bool areIdentical(BSTNode<T> * root1, BSTNode<T> * root2);
    friend bool isSubtree(BSTNode<T> *t, BSTNode<T> *S);
    friend bool isSubTree(BSTFCI<T>* t1, BSTFCI<T>* t2);
};

template<class T2>
bool areIdentical(BSTNode<T2> * root1, BSTNode<T2> *root2)
{
    if (root1 == NULL && root2 == NULL)
        return true;

    if (root1 == NULL || root2 == NULL)
        return false;

    return (root1->key == root2->key &&
            areIdentical(root1->left, root2->left) &&
            areIdentical(root1->right, root2->right) );
}

template<class T2>
bool isSubtree(BSTNode<T2> *t, BSTNode<T2> *S)
{
    if (S == NULL)
        return true;

    if (t == NULL)
        return false;

    if (areIdentical(t, S))
        return true;

    return isSubtree(t->left, S) ||
        isSubtree(t->right, S);
}

template<class T2>
bool isSubTree(BSTFCI<T2>* t1, BSTFCI<T2>* t2){
    return isSubtree(t1->root,t2->root);
}

int main()
{
    BSTFCI <int> * test1 = new BSTFCI <int>();
    BSTFCI <int>* test2 = new BSTFCI <int>();

    test1->Insert(5);
    test1->Insert(7);
    test1->Insert(3);
    test1->Insert(2);
    test1->Insert(9);
    test1->PrintTreeInOrder();

    test2->Insert(5);
    test2->Insert(7);
    test2->Insert(3);
    test2->Insert(2);
    test2->Insert(9);
    test2->PrintTreeInOrder();

    cout<<isSubtree(test1->root,test2->root);
    cout<<isSubTree(test1,test2);

    return 0;
}