I need to rewrite this remove method in a Binary Search Tree class iteratively:

public void remove(AnyType v) { root = remove(v, root); }

private Node remove(AnyType v, Node t) { if (t == null) return t;

int compareResult = v.compareTo(t.getData());

if (compareResult < 0) t.setLeft(remove(v, t.getLeft())); else if (compareResult > 0) t.setRight(remove(v, t.getRight())); else if (t.getLeft() != null && t.getRight() != null) { Node minNodeRightSubtree = findMin(t.getRight()); AnyType minNodeRightSubtreeValue = minNodeRightSubtree.getData(); t.setData(minNodeRightSubtreeValue); // this is the iterative call we can keep t.setRight(remove(minNodeRightSubtreeValue, t.getRight())); } else { Node childOfT = (t.getLeft() != null) ? t.getLeft() : t.getRight(); t = childOfT; }

return t; }

Here is the entire BinarySearchTree class for reference:

import java.util.Iterator; import java.util.LinkedList;

public class BinarySearchTree> { private static class Node { private AnyType data; private Node left; private Node right;

public Node(AnyType d, Node l, Node r) { setData(d); setLeft(l); setRight(r); }

public AnyType getData() { return data; }

public Node getLeft() { return left; }

public Node getRight() { return right; }

public void setData(AnyType d) { data = d; }

public void setLeft(Node l) { left = l; }

public void setRight(Node r) { right = r; } }

private Node root;

public BinarySearchTree() { makeEmpty(); }

public void makeEmpty() { root = null; }

public boolean isEmpty() { return (root == null); }

public boolean contains(AnyType v) { return contains(v, root); }

private boolean contains(AnyType v, Node t) { if (t == null) return false;

int compareResult = v.compareTo(t.getData());

if (compareResult < 0) return contains(v, t.getLeft()); else if (compareResult > 0) return contains(v, t.getRight()); else return true; }

public AnyType findMin() throws IllegalStateException { if (isEmpty()) throw new IllegalStateException("Search Tree is empty.");

Node minNode = findMin(root); return minNode.getData(); }

private Node findMin(Node t) { if (t == null) return null; else if (t.getLeft() == null) return t;

return findMin(t.getLeft()); }

public AnyType findMax() throws IllegalStateException { if (isEmpty()) throw new IllegalStateException("Search Tree is empty.");

Node maxNode = findMax(root); return maxNode.getData(); }

private Node findMax(Node t) { if (t == null) return null; else if (t.getRight() == null) return t;

return findMax(t.getRight()); }

public void insert(AnyType v) {

root = insert(v, root); }

private Node insert(AnyType v, Node t) { // create a new node with the value to be inserted Node node = new Node<>(v, null, null);

// if the root is empty, then set the node to be inserted as the root node if (t == null) return (node);

// declare a parent node initially set to null Node parent = new Node<>(null, null, null);

// and a current node set to the root Node curr = t;

// compare the value of the root to the value you want to insert int compareRoot = v.compareTo(t.getData());

while (curr != null) { // if current isn't null, set the parent equal to current parent = curr; // if value being inserted is less than the root, then move current to // the left if (compareRoot < 0) curr = curr.getLeft(); // else move current to the right else curr = curr.getRight(); }

int compareParent = (parent.getData()).compareTo(v); // if the parent node is less than the current node, insert the current // node to the right if (compareParent < 0) parent.setRight(node); // else insert the node to the left else parent.setLeft(node);

return t; }

/*public void remove(AnyType v) { // Write the iterative version of the remove method here.

}*/ public void remove(AnyType v) { root = remove(v, root); }

private Node remove(AnyType v, Node t) { if (t == null) return t;

int compareResult = v.compareTo(t.getData());

if (compareResult < 0) t.setLeft(remove(v, t.getLeft())); else if (compareResult > 0) t.setRight(remove(v, t.getRight())); else if (t.getLeft() != null && t.getRight() != null) { Node minNodeRightSubtree = findMin(t.getRight()); AnyType minNodeRightSubtreeValue = minNodeRightSubtree.getData(); t.setData(minNodeRightSubtreeValue); // this is the iterative call we can keep t.setRight(remove(minNodeRightSubtreeValue, t.getRight())); } else { Node childOfT = (t.getLeft() != null) ? t.getLeft() : t.getRight(); t = childOfT; }

return t; }

public void printTree() { // Write the code to print out the values in the tree // in a tree like form as described in the assignment // description.

}

public Iterator iterator() { LinkedList snapshot = new LinkedList<>();

inOrderTraversal(root, snapshot); return snapshot.iterator(); }

private void inOrderTraversal(Node t, LinkedList l) { if (t != null) { inOrderTraversal(t.getLeft(), l); l.add(t.getData()); inOrderTraversal(t.getRight(), l); } }