Question

Problem Binary Search Tree Implement the BinarySearchTree class. The BinarySearchTree class extends the BinaryTree class. Both can be seen here. Your assignment is to implement all of the abstract methods of the BinaryTree class recursively. They are: . insert iterator (non-recursive) * remove . search You must also implement an Iterator inner class for the BinarySearchTree class. You must submit a modified BinarySearchTree.java file with your source code. Do not submit and do not modify the BinaryTree.java file Back
What need to be done

What’s given

Answer 1

HI I am providing the BinarySearchTree class as you already have the BinaryTree class and Main class. Let me know if you have any issue

public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {

private Node<E> findIOP(Node<E> curr) {

for (curr = curr.left; curr.right != null; curr = curr.right)

;

return curr;

}

public void insert(E data) {

Node<E> temp = new Node<E>(data);

if (root == null) {

root = temp;

} else {

Node<E> curr = root;

while (true) {

if (data.compareTo(curr.data) <= 0) {

if (curr.left != null) {

curr = curr.left;

} else {

curr.left = temp;

break;

}

} else {

if (curr.right != null) {

curr = curr.right;

} else {

curr.right = temp;

break;

}

}

}

}

}

public Iterator<E> iterator() {

return null;

}

public void remove(E data) {

if (root != null) {

if (data.compareTo(root.data) == 0) {

if (root.left == null || root.right == null) {

root = root.left != null ? root.left : root.right;

} else {

Node<E> iop = findIOP(root);

E temp = root.data;

root.data = iop.data;

iop.data = temp;

if (root.left == iop) {

root.left = root.left.left;

} else {

Node<E> curr = root.left;

while (curr.right != iop) {

curr = curr.right;

}

curr.right = curr.right.left;

}

}

} else {

Node<E> curr = root;

int cmp;

while (true) {

cmp = data.compareTo(curr.data);

if (cmp < 0 && curr.left != null && data.compareTo(curr.left.data) != 0) {

curr = curr.left;

} else if (cmp > 0 && curr.right != null && data.compareTo(curr.right.data) != 0) {

curr = curr.right;

} else {

break;

}

}

if (cmp < 0 && curr.left != null) {

if (curr.left.left == null || curr.left.right == null) {

curr.left = curr.left.left != null ? curr.left.left : curr.left.right;

} else {

Node<E> iop = findIOP(curr.left);

E temp = curr.left.data;

curr.left.data = iop.data;

iop.data = temp;

if (curr.left.left == iop) {

curr.left.left = curr.left.left.left;

} else {

Node<E> node = curr.left.left;

while (node.right != iop) {

node = node.right;

}

node.right = node.right.left;

}

}

} else if (cmp > 0 && curr.right != null) {

if (curr.right.left == null || curr.right.right == null) {

curr.right = curr.right.left != null ? curr.right.left : curr.right.right;

} else {

Node<E> iop = findIOP(curr.right);

E temp = curr.right.data;

curr.right.data = iop.data;

iop.data = temp;

if (curr.right.left == iop) {

curr.right.left = curr.right.left.left;

} else {

Node<E> node = curr.right.left;

while (node.right != iop) {

node = node.right;

}

node.right = node.right.left;

}

}

}

}

}

}

public boolean search(E data) {

Node<E> curr = root;

while (curr != null) {

if (data.compareTo(curr.data) == 0) {

return true;

} else if (data.compareTo(curr.data) < 0) {

curr = curr.left;

} else {

curr = curr.right;

}

}

return false;

}

}