Create a class BinarySearchTree. A class that implements the ADT binary search tree by extending BinaryTree. Recursive version.

public class BinarySearchTree> extends BinaryTree implements SearchTreeInterface { public BinarySearchTree() { super(); } // end default constructor

public BinarySearchTree(T rootEntry) { super(); setRootNode(new BinaryNode<>(rootEntry)); } // end constructor

public void setTree(T rootData) // Disable setTree (see Segment 25.6) { throw new UnsupportedOperationException(); } // end setTree

public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { throw new UnsupportedOperationException(); } // end setTree

//...

public T remove(T entry) { ReturnObject oldEntry = new ReturnObject(null); BinaryNode newRoot = removeEntry(getRootNode(), entry, oldEntry); setRootNode(newRoot);

return oldEntry.get(); } // end remove

//...

private class ReturnObject { private T item; private ReturnObject(T entry) { item = entry; } // end constructor public T get() { return item; } // end get

public void set(T entry) { item = entry; } // end set } // end ReturnObject } // end BinarySearchTree HERE IS BinaryTree.java

import java.util.Iterator; import java.util.NoSuchElementException;

public class BinaryTree implements BinaryTreeInterface {

private BinaryNode root;

public BinaryTree() { root = null; }

public BinaryTree(T rootData) { root = new BinaryNode<>(rootData); }

public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { privateSetTree(rootData, leftTree, rightTree); }

private void privateSetTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { root = new BinaryNode<>(rootData);

if (leftTree != null && !leftTree.isEmpty()) { root.setLeftChild(leftTree.root); }

if (rightTree != null && !rightTree.isEmpty()) { if (rightTree != leftTree) { root.setRightChild(rightTree.root); } else { root.setRightChild(rightTree.root.copy()); } }

if (leftTree != null && leftTree != this) { leftTree.clear(); }

if (rightTree != null && rightTree != this) { rightTree.clear(); } }

@Override public T getRootData() { if (isEmpty()) { throw new EmptyTreeException("The tree is empty."); } return root.getData(); }

@Override public int getHeight() { return root.getHeight(); }

@Override public int getNumberOfNodes() { return root.getNumberOfNodes(); }

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

@Override public void clear() { root = null; }

@Override public Iterator getPreorderIterator() { return new PreorderIterator(); }

@Override public Iterator getInorderIterator() { return new InorderIterator(); }

@Override public Iterator getPostorderIterator() { return new PostorderIterator(); }

private class PreorderIterator implements Iterator { private StackInterface> nodeStack;

public PreorderIterator() { nodeStack = new LinkedStack<>(); if (root != null) { nodeStack.push(root); } }

public boolean hasNext() { return !nodeStack.isEmpty(); }

public T next() { BinaryNode nextNode;

if (hasNext()) { nextNode = nodeStack.pop(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild();

if (rightChild != null) { nodeStack.push(rightChild); }

if (leftChild != null) { nodeStack.push(leftChild); } } else { throw new NoSuchElementException(); }

return nextNode.getData(); }

public void remove() { throw new UnsupportedOperationException(); } }

private class InorderIterator implements Iterator { private StackInterface> nodeStack; private BinaryNode currentNode;

public InorderIterator() { nodeStack = new LinkedStack<>(); currentNode = root; }

public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); }

public T next() { BinaryNode nextNode = null;

while (currentNode !=null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } if (!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); currentNode = nextNode.getRightChild(); } else { throw new NoSuchElementException(); }

return nextNode.getData(); }

public void remove() { throw new UnsupportedOperationException(); } }

private class PostorderIterator implements Iterator { private StackInterface> nodeStack; private BinaryNode currentNode; private BinaryNode lastNodeVisited; public PostorderIterator() { nodeStack = new LinkedStack<>(); currentNode = root; lastNodeVisited = null; }

public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); }

public T next() { BinaryNode leftChild, rightChild, nextNode = null;

while (currentNode != null) { nodeStack.push(currentNode); leftChild = currentNode.getLeftChild(); if (leftChild == null) { currentNode = currentNode.getRightChild(); } else { currentNode = leftChild; } }

// stack is not empty, pop top node if (!nodeStack.isEmpty()) { nextNode = nodeStack.pop();

BinaryNode parent = null; if (!nodeStack.isEmpty()) { parent = nodeStack.peek(); if (nextNode == parent.getLeftChild()) { currentNode = parent.getRightChild(); } else { currentNode = null; } } else { currentNode = null; } } else { throw new NoSuchElementException(); }

return nextNode.getData(); }

public void remove() { throw new UnsupportedOperationException(); }//end remove }

@Override public Iterator getLevelOrderIterator() { return null; }

@Override public void setTree(T rootData) { }

@Override public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { } }//end BinaryTree