@Override
	public void insert(K k) {

		// induction basis:
		BinarySearchTreeItem<K> p;
		if (root == null) {
			p = new BinarySearchTreeItem<K>(k);
			p.left = null;
			p.right = null;
		} else {
			p = root;
		}

		// induction step:
		while (true) {
			if (p.key == k) {
				if (p.left == null) {
					p.left = new BinarySearchTreeItem<K>(k);
					p.left.left = null;
					p.left.right = null;
					break;
				} else if (p.right == null) {
					p.right = new BinarySearchTreeItem<K>(k);
					p.right.left = null;
					p.right.right = null;
					break;
				} else {
					p = p.left;
				}
			} else if ((Integer) p.key > (Integer) k) {
				if (p.left == null) {
					p.left = new BinarySearchTreeItem<K>(k);
					p.left.left = null;
					p.left.right = null;
					break;
				} else {
					p = p.left;
				}
			} else if ((Integer) p.key < (Integer) k) {
				if (p.right == null) {
					p.right = new BinarySearchTreeItem<K>(k);
					p.right.left = null;
					p.right.right = null;
					break;
				} else {
					p = p.right;
				}
			}
		}
	}