#include "lab1.h"
#include "lab2.h"
#include "lab3.h"

using namespace std;

void dfs1(lab3::TreeNode* root){
    if(root == nullptr){
        return;
    } else {
        cout << root->val << ' ';
        dfs1(root->left);
        dfs1(root->right);
    }
}

void dfs2(lab3::TreeNode* root){
    if(root == nullptr){
        return;
    } else{
        dfs2(root->left);
        cout << root->val;
        dfs2(root->right);
    }
}

bool Compare(int val, lab3::TreeNode* tree){
    if(tree == nullptr)
        return false;
    if(tree->val == val)
        return true;
    return Compare(val, tree->left) || Compare(val, tree->right);
}

int findMinEl(lab3::TreeNode*& root){
    if(root->left == nullptr){
        int val = root->val;
        delete root;
        root = nullptr;
        return val;
    } else {
        return findMinEl(root->left);
    }
}

void DeleteNode(lab3::TreeNode *&root){
    if(root == nullptr)
        return;
    else if(root->left == nullptr&& root->right == nullptr){
        delete root;
        root = nullptr;
    } else if(root->left != nullptr&& root->right == nullptr){
        lab3::TreeNode *tmp = root->left;
        delete root;
        root = tmp;
    } else if(root->left == nullptr&& root->right != nullptr){
        lab3::TreeNode *tmp = root->right;
        delete root;
        root = tmp;
    } else {
        root->val = findMinEl(root->right);
    }
}



void multiplie(lab3::TreeNode*& a, lab3::TreeNode* b){
    while (a != nullptr){
        if(Compare(a->val, b)){
            multiplie(a->left, b);
            multiplie(a->right, b);
            break;
        } else {
            DeleteNode(a);
            multiplie(a, b);
        }
    }
}

int main(){
    lab3::TreeNode *root1 = nullptr, *root2 = nullptr;
    vector<int> v1 = {5,8,6,9,3}, v2 = {6,4,8,3,7};
    for(int i = 0; i < v1.size(); ++i) {
        lab3::Add(root1, v1[i]);
        lab3::Add(root2, v2[i]);
    }
    multiplie(root1, root2);
    dfs1(root1);
}