#ifndef __BST
#define __BST

#include <iostream> 

/* Узел дерева. */
template <typename T>
struct TreeNode {
	T _data;
	TreeNode<T> * _parent, * _left, * _right;

	TreeNode(T data) : _data(data), _parent(nullptr),
		_left(nullptr), _right(nullptr) {}

	TreeNode(T data, TreeNode<T> * parent) : _data(data), 
		_parent(parent), _left(nullptr), _right(nullptr) {}

	TreeNode(T data, TreeNode<T> * left, TreeNode<T> * right) : 
		_data(data), _parent(nullptr), _left(left), _right(right) {}

	TreeNode(T data, TreeNode<T> * parent, TreeNode<T> * left, TreeNode<T> * right) :
		_data(data), _parent(parent), _left(left), _right(right) {}
};

/* Бинарное дерево поиска без повторений. */
template <typename T>
struct BinSearchTree {
	TreeNode<T> * _root;

private:
	/* Вспомогательная функция для функции insert. */
	void insert(TreeNode<T> * current_node, TreeNode<T> * parent, T value) {
		if (!current_node) {
			current_node = new TreeNode<T>(value, parent);
			return;
		}

		if (value < current_node->_data)
			insert(current_node->_left, current_node, value);
		else if (value > current_node->_data)
			insert(current_node->_right, current_node, value);
	}

	/* Вспомогательная функция для функции print. */
	void print(TreeNode<T> * node) {
		if (!node)
			return;

		print(node->_left);
		std::cout << node->_data << ' ';
		print(node->_right);
	}

public:
	BinSearchTree() : _root(nullptr) {}

	BinSearchTree(TreeNode<T> * root) : _root(root) {}

	BinSearchTree(T data) : _root(new TreeNode<T>(data)) {}

	/* Печатает содержимое дерева на экран по возрастанию (ЛКП).*/
	void print() {
		if (!_root)
			return;

		print(_root->_left);
		std::cout << _root->_data << ' ';
		print(_root->_right);
	}

	/* Вставляет элемент в БДП. */
	void insert(T value) {
		if (!_root) {
			_root = new TreeNode<T>(value);
			return;
		}

		if (value < _root->_data)
			insert(_root->_left, _root, value);
		else if (value > _root->_data)
			insert(_root->_right, _root, value);
	//	std::cout << _root->_right;
	}
};

#endif /* __BST */