template <typename T>
class set {
public:
	class node {
	public:
		node* right;
		node* left;
		int key;

		node() {
			key = 0;
			right = nullptr;
			left = nullptr;
		}

		node(int key) {
			this->key = key;
			right = nullptr;
			left = nullptr;
		}
	};

	node* root;

	set() {
		root = nullptr;
	}

	void push(node* parent, int key) {
		if (key > parent->key) {
			if (parent->right == nullptr)
				parent->right = new node(key);
			else
				push(parent->right, key);
		}
		else {
			if (key < parent->key) {
				if (parent->left == nullptr)
					parent->left = new node(key);
				else
					push(parent->left, key);
			}
		}
	}

	void push(int key) {
		if (root == nullptr)
			root = new node(key);
		else
			push(root, key);
	}

	void print(node* parent) {
		if (parent->left != nullptr)
			print(parent->left);

		cout << "{" << parent->key << "} ";

		if (parent->right != nullptr)
			print(parent->right);
	}

	void print() {
		print(root);
	}


	node* find(node * parent, int key) {
		где-то <= или >= для multiset ???
		node* r = nullptr;
		if (key > parent->key) {
			if (parent->right != nullptr)
				r = find(parent->right, key);
		}
		else {
			if (key < parent->key) {
				if (parent->left != nullptr)
					r = find(parent->left, key);
			}
			else {
				r = parent;
			}
		}

		return r;
	}

	node* find(int key) {
		return find(root, key);
	}

	static void set_intersection(set & s3, set & s2, node * parent) {

		if (parent->left)
			set_intersection(s3, s2, parent->left);

		node* f = s2.find(parent->key);

		if (f != nullptr)
			s3.push(parent->key);

		if (parent->right)
			set_intersection(s3, s2, parent->right);
	}

	возращает те элементы которые пересечение
	static set set_intersection(set & s1, set & s2) {
		set s3;

		set_intersection(s3, s2, s1.root);

		return s3;
	}

	объединение
	static void set_union(set & s3, node * parent) {

		if (parent->left)
			set_union(s3, parent->left);

		s3.push(parent->key);

		if (parent->right)
			set_union(s3, parent->right);

	}

	Возвращает множество объединения s1 и s2
	static set set_union(set & s1, set & s2) {
		set s3;

		set_union(s3, s1.root);

		set_union(s3, s2.root);

		return s3;
	}


	static void set_difference(set & s3, set & s2, node * parent) {

		if (parent->left)
			set_difference(s3, s2, parent->left);

		node* f = s2.find(parent->key);
		if (f == nullptr)
			s3.push(parent->key);

		if (parent->right)
			set_difference(s3, s2, parent->right);
	}
	Находит одинаковые элементы в двух множествая и создает новое множество без них
	static set set_difference(set & s1, set & s2) {
		set s3;

		set_difference(s3, s2, s1.root);

		set_difference(s3, s1, s2.root);

		return s3;
	}

	class iterator {
	public:
		node* current;
		stack<node*> s;

		iterator(node* n) {
			current = n;
		}

		void findn() {
			if (current->right != NULL) {
				s.push(current);
				current = set::findl(current->right);
			}
			else {
				node* parent = current->parent;

				if (!s.empty()) {

					node* top = s.top();
					while (top == parent) {
						parent = top->parent;
						s.pop();
						if (s.empty())
							break;
						top = s.top();
					}

					current = parent;
				}
			}
		}

		bool operator !=(iterator other) {
			return current != other.current;
		}
		iterator operator++() {
			findn();
			return *this;
		}

		iterator operator++(int) {
			findn();
			return *this;
		}

		T operator *() {
			return current->key;
		}
	};

	iterator begin() {
		return iterator(findl(root));
	}

	iterator end() {
		return iterator(NULL);
	}
};