import java.util.ArrayList;
import java.util.List;

class BinTree<T extends Comparable> {

	public Node first = new Node();

	public void insert(T elem) {
		first.insert(elem);
	}

	public void remove(T elem) {
		first = remove(elem, first);
	}
	public Node remove(T elem, Node n) {
		if (n == null) return null;

		if (elem.compareTo(n.elem) < 0) {
			n.left = remove(elem, n.left);
			if (n.left != null) n.left.parent = n;
		} else if (elem.compareTo(n.elem) < 0) {
			n.right = remove(elem, n.right);
			if (n.right != null) n.right.parent = n;
		} else {
			if (n.left == null) {
				Node p = n.parent;
				n = n.right;
				if (n != null) n.parent = p;
			} else if (n.right == null) {
				Node p = n.parent;
				n = n.left;
				if (n != null) n.parent = p;
			} else {
				n.elem = n.right.findSmallest();
				n.right = remove(n.elem, n.right);
				n.right.parent = n;
			}
		}
		return n;
	}

	public Node search(T elem) {
		return first.search(elem);
	}

	public T findSmallest() {
		return first.findSmallest();
	}

	public T findBiggest() {
		return first.findBiggest();
	}

	public List<Node> findSimilar(T str) throws Exception {
		if (!(str instanceof String))
			throw new Exception("findSimilar only works on string trees");

		List<Node> similar = new ArrayList<>();

		for (String s: SpellUtils.similarWords((String)str)) {
			Node n = this.search((T)s);
			if (n != null)
				similar.add(n);
		}

		// Deduplicate
		List<Node> exists = new ArrayList<>();
		List<Node> res = new ArrayList<>();
		for (Node n: similar) {
			if (!exists.contains(n)) {
				exists.add(n);
				res.add(n);
			}
		}

		return res;
	}

	class Node {
		public Node left = null;
		public Node right = null;
		public Node parent;

		public T elem;

		public Node(Node parent) {
			this.parent = parent;
		}
		public Node() {
			this.parent = null;
		}

		public void insert(T elem) {
			if (this.elem == null) {
				this.elem = elem;

			} else if (this.elem.compareTo(elem) > 0) {
				if (this.left == null) {
					this.left = new Node(this);
				}

				this.left.insert(elem);

			} else {
				if (this.right == null) {
					this.right = new Node(this);
				}

				this.right.insert(elem);
			}
		}

		public T findSmallest() {
			if (this.left != null)
				return this.left.findSmallest();
			else
				return this.elem;
		}

		public T findBiggest() {
			if (this.right != null)
				return this.right.findBiggest();
			else
				return this.elem;
		}

		public Node search(T elem) {
			int cmp = this.elem.compareTo(elem);
			if (cmp == 0)
				return this;
			else if (cmp > 0 && this.left != null)
				return this.left.search(elem);
			else if (this.right != null)
				return this.right.search(elem);
			else
				return null;
		}

		public int depth() {
			int d = 0;
			Node n = this.parent;
			while (n != null) {
				d += 1;
				n = n.parent;
			}
			return d;
		}
	}
}