//
//  main.cpp
//  lab9_tree
//
//  Created by AND on 17/05/2019.
//  Copyright © 2019 Andrey Popov. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10
using namespace std;


struct Tree {
    int value;
    Tree *left;
    Tree *right;
};

//th - tree head
void add_node(Tree *th, int value) {
    if (th == NULL) {
        th = new Tree;
        th->value = value;
        th->left = NULL;
        th->right = NULL;
    }
    else {
        if (value > th->value) add_node(th->right, value);
        else add_node(th->left, value);
    }
}


void preorder(Tree *node){
    if (node) {
        cout << node->value << " ";
        preorder(node->left);
        preorder(node->right);
    }
}


int tree_height(Tree *node){
    int h1=0, h2=0;
    if (node == NULL) return 0;
    if (node->left){
        h1 = tree_height(node->left);
    }
    if (node->right){
        h2 = tree_height(node->right);
    }
    return (max(h1, h2) + 1);
}


int count_nodes(Tree *node){
    if (node == NULL) return 0;
    int c1 = 0, c2 = 0;
    if (node->left){
        c1 = count_nodes(node->left);
    }
    if (node->right){
        c2 = count_nodes(node->right);
    }
    return (c1 + c2 + 1);
}


void copy_tree(Tree * th, Tree * new_tree) {
    if (th){
    new_tree = new Tree;
    new_tree->value = th->value;
    new_tree->left = NULL;
    new_tree->right = NULL;
    copy_tree(th->left, new_tree->left);
    copy_tree(th->right, new_tree->right);
    }
}


void mirror_tree(Tree * th, Tree * mirror_tree){
    if (th){
        mirror_tree = new Tree;
        mirror_tree->value = th->value;
        mirror_tree->left = NULL;
        mirror_tree->right = NULL;
        copy_tree(th->left, mirror_tree->right);
        copy_tree(th->right, mirror_tree->left);
    }
}


int compare_trees(Tree * th1, Tree * th2){
    if (th1 != NULL & th2 != NULL){
        if (th1->value == th2->value){
            int b1 = compare_trees(th1->left, th2->left);
            int b2 = compare_trees(th1->right, th2->right);
            return b1 & b2;
        }
    }else return 0;
    return 0;
}


void find_node(Tree * th, int value){
    if (th == NULL) cout << "404 - not found";
    else{
        int root = th->value;
        cout << root << " ";
        if (value > root) find_node(th->right, value);
        else if (value < root) find_node(th->left, value);
    }
}


int main() {
    int num;
    Tree * my_tree = NULL;
    Tree * new_tree = NULL;
    for (int i = 0; i < 8; i++){
        cin >> num;
        add_node(my_tree, num);
    }
    cout << "\n";
    preorder(my_tree);
    cout << "\n";
    copy_tree(my_tree, new_tree);
    preorder(new_tree);
    mirror_tree(my_tree, new_tree);
    cout << "\n";
    preorder(new_tree);
    cout << "\n" << "height is\t" << tree_height(my_tree) << "\n";
    cout << "quantity of nodes is\t" << count_nodes(my_tree) << "\n";
    cout << "search 20\n";
    find_node(my_tree, 20);
    cout << "\n";
    return 0;
}