struct Node {
    int data;
    Node * left;
    Node *right;
};
void show(Node *tree) {
    if (tree == NULL) return;
    show(tree->left);
    cout << tree->data << " ";
    show(tree->right);
}
void newNode(int x, Node *&root) {
    if (root == NULL) {
        root = new Node();
        root->data = x;
        root->left = root->right = NULL;
    }
    if (x < root->data) {
        if (root->left != NULL) newNode(x, root->left);
        else {
            root->left = new Node();
            root->left->data = x;
            root->left->left = root->left->right = NULL;
        }
    }
    if (x > root->data) {
        if (root->right != NULL) newNode(x, root->right);
        else {
            root->right = new Node();
            root->right->data = x;
            root->right->left = root->right->right = NULL;
        }
    }
}
int search(int x, Node *tree) {
    if (tree == NULL) return 0;
    if (tree->data == x) return 1;
    if (tree->data > x) {
        return search(x, tree->left);
    }
    if (tree->data < x) {
        return search(x, tree->right);
    }
}
int max(int a, int b) {
    if (a > b) return a;
    else return b;
}
int hight(Node *tree) {
    if (tree == NULL) return 0;
    return max(hight(tree->left), hight(tree->right)) + 1;
}