// naive binary search tree with find
#include <random>
#include <iostream>
using namespace std;

//random_device dev;
//mt19937 gen (dev ());
mt19937 gen (1234567890);

struct Node;
using PNode = Node *;
struct Node
{
	int x;
	int y;
	PNode left;
	PNode right;

	Node (int x_)
	{
		x = x_;
		y = uniform_int_distribution <int> (0, 1E9) (gen);
		left = nullptr;
		right = nullptr;
	}
};

PNode naiveInsert (PNode t, int x)
{
	if (t == nullptr)
	{
		PNode n = new Node (x);
		return n;
	}
	if (t -> x < x)
	{
		t -> right = naiveInsert (t -> right, x);
		return t;
	}
	else
	{
		t -> left = naiveInsert (t -> left, x);
		return t;
	}
}

bool tFind (PNode t, int x)
{
	if (t == nullptr)
	{
		return false;
	}
	if (t -> x == x)
	{
		return true;
	}
	if (t -> x < x)
	{
		return tFind (t -> right, x);
	}
	else
	{
		return tFind (t -> left, x);
	}
}

void tOutputRecur (PNode t)
{
	if (t == nullptr)
	{
		return;
	}
	cout << "(";
	tOutputRecur (t -> left);
	cout << t -> x;
	tOutputRecur (t -> right);
	cout << ")";
}

void tOutput (PNode t)
{
	tOutputRecur (t);
	cout << endl;
}

int main ()
{
	PNode root = nullptr;
	tOutput (root);
	root = naiveInsert (root, 5);
	tOutput (root);
	root = naiveInsert (root, 7);
	tOutput (root);
	root = naiveInsert (root, 2);
	tOutput (root);
	root = naiveInsert (root, 1);
	tOutput (root);
	root = naiveInsert (root, 3);
	tOutput (root);
	for (int i = 1; i <= 10; i++)
	{
		cout << tFind (root, i);
	}
	return 0;
}