I need to rewrite this remove method in a Binary Search Tree class iteratively:
ID: 3866785 • Letter: I
Question
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<AnyType> remove(AnyType v, Node<AnyType> 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<AnyType> 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<AnyType> 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<AnyType extends Comparable<? super AnyType>> {
private static class Node<AnyType> {
private AnyType data;
private Node<AnyType> left;
private Node<AnyType> right;
public Node(AnyType d, Node<AnyType> l, Node<AnyType> r) {
setData(d);
setLeft(l);
setRight(r);
}
public AnyType getData() {
return data;
}
public Node<AnyType> getLeft() {
return left;
}
public Node<AnyType> getRight() {
return right;
}
public void setData(AnyType d) {
data = d;
}
public void setLeft(Node<AnyType> l) {
left = l;
}
public void setRight(Node<AnyType> r) {
right = r;
}
}
private Node<AnyType> 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<AnyType> 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<AnyType> minNode = findMin(root);
return minNode.getData();
}
private Node<AnyType> findMin(Node<AnyType> 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<AnyType> maxNode = findMax(root);
return maxNode.getData();
}
private Node<AnyType> findMax(Node<AnyType> 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<AnyType> insert(AnyType v, Node<AnyType> t) {
// create a new node with the value to be inserted
Node<AnyType> 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<AnyType> parent = new Node<>(null, null, null);
// and a current node set to the root
Node<AnyType> 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<AnyType> remove(AnyType v, Node<AnyType> 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<AnyType> 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<AnyType> 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<AnyType> iterator() {
LinkedList<AnyType> snapshot = new LinkedList<>();
inOrderTraversal(root, snapshot);
return snapshot.iterator();
}
private void inOrderTraversal(Node<AnyType> t, LinkedList<AnyType> l) {
if (t != null) {
inOrderTraversal(t.getLeft(), l);
l.add(t.getData());
inOrderTraversal(t.getRight(), l);
}
}
Explanation / Answer
public void remove(AnyType v) { root = remove(v, root); }
private Node<AnyType> remove(AnyType v, Node<AnyType> 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<AnyType> 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<AnyType> 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<AnyType extends Comparable<? super AnyType>> {
private static class Node<AnyType> {
private AnyType data;
private Node<AnyType> left;
private Node<AnyType> right;
public Node(AnyType d, Node<AnyType> l, Node<AnyType> r) {
setData(d);
setLeft(l);
setRight(r);
}
public AnyType getData() {
return data;
}
public Node<AnyType> getLeft() {
return left;
}
public Node<AnyType> getRight() {
return right;
}
public void setData(AnyType d) {
data = d;
}
public void setLeft(Node<AnyType> l) {
left = l;
}
public void setRight(Node<AnyType> r) {
right = r;
}
}
private Node<AnyType> 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<AnyType> 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<AnyType> minNode = findMin(root);
return minNode.getData();
}
private Node<AnyType> findMin(Node<AnyType> 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<AnyType> maxNode = findMax(root);
return maxNode.getData();
}
private Node<AnyType> findMax(Node<AnyType> 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<AnyType> insert(AnyType v, Node<AnyType> t) {
// create a new node with the value to be inserted
Node<AnyType> 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<AnyType> parent = new Node<>(null, null, null);
// and a current node set to the root
Node<AnyType> 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<AnyType> remove(AnyType v, Node<AnyType> 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<AnyType> 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<AnyType> 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<AnyType> iterator() {
LinkedList<AnyType> snapshot = new LinkedList<>();
inOrderTraversal(root, snapshot);
return snapshot.iterator();
}
private void inOrderTraversal(Node<AnyType> t, LinkedList<AnyType> l) {
if (t != null) {
inOrderTraversal(t.getLeft(), l);
l.add(t.getData());
inOrderTraversal(t.getRight(), l);
}
}