#include <stdio.h>
#include <iostream>
using namespace std;
struct Node {
    int data;
    Node * left;
    Node *right;
    Node(int x) {
        data = x;
        left = right = NULL;
    }
};
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(x);
    if (x < root->data) {
        if (root->left != NULL) newNode(x, root->left);
        else  root->left = new Node(x);
    }
    if (x > root->data) {
        if (root->right != NULL) newNode(x, root->right);
        else  root->right = new Node(x);
    }
}
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;
}