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

struct TreeNode {
    int val;
    vector<TreeNode*> children;
    TreeNode(int v) : val(v) {}
};

bool compareTrees(TreeNode* t1, TreeNode* t2) {
    if (!t1 && !t2) return true;
    if (!t1 || !t2) return false;
    if (t1->val != t2->val) return false;
    
    if (t1->children.size() != t2->children.size()) return false;
    
    for (int i = 0; i < t1->children.size(); ++i) {
        if (!compareTrees(t1->children[i], t2->children[i])) {
            return false;
        }
    }
    
    return true;
}

bool findLocation(TreeNode* t1, TreeNode* t2) {
    if (!t1 || !t2) return false;
    
    if (compareTrees(t1, t2)) {
        return true;
    }
    
    for (TreeNode* child : t2->children) {
        if (findLocation(t1, child)) {
            return true;
        }
    }
    
    return false;
}

TreeNode* buildTree() {
    int val, childCount;
    cout << "Enter value for node: ";
    cin >> val;
    TreeNode* root = new TreeNode(val);
    
    cout << "Enter number of children for node " << val << ": ";
    cin >> childCount;
    
    for (int i = 0; i < childCount; ++i) {
        TreeNode* child = buildTree();
        root->children.push_back(child);
    }
    
    return root;
}

void levelOrderTraversal(TreeNode* root) {
    if (!root) return;
    
    queue<TreeNode*> q;
    q.push(root);
    q.push(nullptr);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node == nullptr){
            
            if(!q.empty()){
                q.push(nullptr);
            }
        } else{
            
        cout << node->val << " ";
        
        for (TreeNode* child : node->children) {
            q.push(child);
        }
    }
}
    cout << endl;
}
/*void levelOrderTraversal(TreeNode* root) {
    if (!root) return;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        
        for (TreeNode* child : node->children) {
            q.push(child);
        }
    }
    
    cout << endl;
}*/

int main() {
    cout << "Enter the first tree:" << endl;
    TreeNode* tree1 = buildTree();
    
    cout << "Enter the second tree:" << endl;
    TreeNode* tree2 = buildTree();
    
    if (findLocation(tree1, tree2)) {
        cout << "Tree 1 is located within Tree 2." << endl;
    } else {
        cout << "Tree 1 is not located within Tree 2." << endl;
    }
    
    cout << "Level order traversal of Tree 2: ";
    levelOrderTraversal(tree2);
    
    
    
    return 0;
}