#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;
    }

    template <typename T2>
    friend bool areIdentical(BSTNode<T2> * root1, BSTNode<T2> * root2);
    template <typename T2>
    friend bool isSubtree(BSTNode<T2> *t, BSTNode<T2> *S);
    template <typename T2>
    friend bool isSubTree(BSTFCI<T2>* t1, BSTFCI<T2>* 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;
}