#include <iostream>

using namespace std;

template<typename T>
class Node {
public:
	Node<T> *left, *right, *parent;
	T key;

	Node(T key) {
		left = right = parent = NULL;
		this->key = key;
	}

};

template<typename T>
class BST {
public:
	Node<T> *root;

	BST() {
		root = NULL;
	}

	bool insert(const T& dane) {

		Node<T> *x = root;
		Node<T> *y = root;
		if (root == NULL) {
			root = new Node<T>(dane);
			return true;
		}
		else {
			Node<T> * temp = new Node<T>(dane);
			while (x != NULL) {
				if (x->key == dane) {

					return false;
				}
				else if (dane < x->key) {
					y = x;
					x = x->left;
				}
				else {
					y = x;
					x = x->right;
				}
			}

			if (y->key < dane) {
				y->left = temp;
				temp->parent = y;
			}
			else {
				y->right = temp;
				temp->parent = y;
			}
		}
		return true;
	}

	void PREORDER(Node<T> * dane)
	{
		cout << dane->key << endl;
		if (dane->left != NULL) PREORDER(dane->left);
		if (dane->right != NULL) PREORDER(dane->right);
	}

};
int main(int argc, char** argv) {

	BST<int> tmp;

	tmp.insert(90);
	tmp.insert(85);
	tmp.insert(24);
	tmp.insert(5);
	tmp.insert(74);

	tmp.PREORDER(tmp.root);
	/*tmp.insert(xd);
	xd = new Node(85);
	tmp.insert(xd);
	tmp.PREORDER(tmp.root);
	xd = new Node(24);
	tmp.insert(xd);
	xd = new Node(60);
	tmp.insert(xd);
	xd = new Node(75);
	tmp.insert(xd);
	xd = new Node(85);
	tmp.insert(xd);
	xd = new Node(85);
	tmp.insert(xd);
	xd = new Node(5);
	tmp.insert(xd);*/




	return 0;
}