Krisi_Trees

#include "stdafx.h"

struct elem {
    int key;
    elem* left;
    elem* right;
};

bool areIdentical(elem *root1, elem *root2) {
    if (root1 == nullptr && root2 == nullptr)
        return true;

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

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

bool contained(elem *T, elem *S) {
    if (S == nullptr)
        return true;

    if (T == nullptr)
        return false;

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

    return contained(T->left, S) ||
        contained(T->right, S);
}

elem* addElem(int key) {
    elem* node = new elem;
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    return(node);
}

int main() {
    elem *T = addElem(26);
    T->right = addElem(3);
    T->right->right = addElem(3);
    T->left = addElem(10);
    T->left->left = addElem(4);
    T->left->left->right = addElem(30);
    T->left->right = addElem(6);

    elem *S = addElem(10);
    S->right = addElem(6);
    S->left = addElem(4);
    S->left->right = addElem(30);

    cout << (contained(T, S) ? "Tree 2 is contained in Tree 1\n" : "Tree 2 is not contained in Tree 1\n");

    return 0;
}