#include <iostream>
using namespace std;

struct node
{
	int storage;
	node* left;
	node* right;
};

node* root = NULL;

node* GetNewNode(int info)
{
	node* newNode = new node();
	newNode->storage = info;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}

node* insert(node* root, int info)
{
	if (root == NULL)
	{
		root = GetNewNode(info);
		return root;
	}
	else if (info <= root->storage)
	{
		root->left = insert(root->left, info);
	}
	else
	{
		root->right = insert(root->right, info);
	}
	return root;
}

void displayPreOrder(node* root)
{
	if (root != NULL)
	{
		cout << root->storage << " ";
		displayPreOrder(root->left);
		displayPreOrder(root->right);
	}
}

void displayPostOrder(node* root)
{
	if (root != NULL)
	{
		displayPostOrder(root->left);
		displayPostOrder(root->right);
		cout << root->storage << " ";
	}
}

void displayInOrder(node* root)
{
	if (root != NULL)
	{
		displayInOrder(root->left);
		cout << root->storage << " ";
		displayInOrder(root->right);
	}
}

bool search(node* root, int info)
{
	if (root == NULL)
		return false;
	else if (root->storage == info)
		return true;
	else if (info <= root->storage)
		return search(root->left, info);
	else
		return search(root->right, info);
}

void find(node* root)
{
	int number;
	cout << "Scrie numarul pe care vrei sa-l cauti: ";
	cin >> number;
	if (search(root, number) == true)
		cout << "Gasit" << "\n";
	else
		cout << "Nu a fost gasit" << "\n";
}

int main()
{
	int lungime, valoare;
	cout << "Lungimea sirului: ";
	cin >> lungime;
	for (int i = 1; i <= lungime; i++)
	{
		cout << "Scrie elementul " << i << ": ";
		cin >> valoare;
		root = insert(root, valoare);
	}
}