(Solved): As a lab exercise 23.5 A Do-It-Yourself BST, fill in the blanks in the removeRoot method in JM\Ch23\ ...

As a lab exercise 23.5 A Do-It-Yourself BST, fill in the blanks in the removeRoot method in JM\Ch23\BST\MyTreeSet.java. For “extra credit,” make MyTreeSet Iterable by implementing an iterator method and a MyTreeSetIterator class. See Section for an example. Your iterator should perform inorder traversal of the tree: left subtree, root, right subtree. Use a Stack in your MyTreeSetIterator class. Do not implement the remove method for your iterator.

Please refer the screenshot images from 1 to 6.jpg

MyTreeSet.java

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

/**
Implements a BST with TreeNode nodes.

@author TODO Your Name
@version TODO Date

@author Period - TODO Your Period
@author Assignment - TODO Assignment Name

@author Sources - TODO list collaborators
*/
public class MyTreeSet<E> implements Iterable<E>
{
private TreeNode<E> root; // holds the root of this BST

// Constructor: creates an empty BST.
public MyTreeSet()
{
root = null;
}

// Returns true if this BST contains value; otherwise returns false.
public boolean contains( E value )
{
return contains( root, value );
}

// Adds value to this BST, unless this tree already holds value.
// Returns true if value has been added; otherwise returns false.
public boolean add( E value )
{
if ( contains( value ) )
return false;
root = add( root, value );
return true;
}

// Removes value from this BST. Returns true if value has been
// found and removed; otherwise returns false.
public boolean remove( E value )
{
if ( !contains( value ) )
return false;
root = remove( root, value );
return true;
}

// Returns a string representation of this BST.
public String toString()
{
String str = toString( root );
if ( str.endsWith( ", " ) )
str = str.substring( 0, str.length() - 2 );
return "[" + str + "]";
}

// Returns an iterator for this BST.
public Iterator<E> iterator()
{
// Complete method
return the iterator; // Fix this!!
}

//*************** Private helper methods: *********************

// Returns true if the BST rooted at node contains value;
// otherwise returns false (recursive version).
private boolean contains( TreeNode<E> node, E value )
{
if ( node == null )
return false;
else
{
int diff = ( (Comparable<E>)value ).compareTo( node.getValue() );
if ( diff == 0 )
return true;
else if ( diff < 0 )
return contains( node.getLeft(), value );
else // if (diff > 0)
return contains( node.getRight(), value );
}
}

/*
// Iterative version:
private boolean contains(TreeNode<E> node, E value)
{
while (node != null)
{
int diff = ( (Comparable<E>)value).compareTo( node.getValue() );
if (diff == 0)
return true;
else if (diff < 0)
node = node.getLeft();
else // if (diff > 0)
node = node.getRight();
}
return false;
}
*/

// Adds value to the BST rooted at node. Returns the
// root of the new tree.
// Precondition: the tree rooted at node does not contain value.
private TreeNode<E> add( TreeNode<E> node, E value )
{
if ( node == null )
node = new TreeNode( value );
else
{
int diff = ( (Comparable<E>)value ).compareTo( node.getValue() );
if ( diff < 0 )
node.setLeft( add( node.getLeft(), value ) );
else // if (diff > 0)
node.setRight( add( node.getRight(), value ) );
}
return node;
}

// Removes value from the BST rooted at node.
// Returns the root of the new tree.
// Precondition: the tree rooted at node contains value.
private TreeNode<E> remove( TreeNode<E> node, E value )
{
int diff = ( (Comparable<E>)value ).compareTo( node.getValue() );
if ( diff == 0 ) // base case
node = removeRoot( node );
else if ( diff < 0 )
node.setLeft( remove( node.getLeft(), value ) );
else // if (diff > 0)
node.setRight( remove( node.getRight(), value ) );
return node;
}

// Removes the root of the BST rooted at root
// replacing it with the smallest node from the right subtree.
// Returns the root of the new tree.
private TreeNode<E> removeRoot(TreeNode<E> root)
{
TreeNode<E> node = root.getRight();

// TODO complete method

return node;
}

// Utility routine to print the structure of the BST
public void printSideways()
{
if (root == null)
return;
printSideways(root, 0);
}

// Precondition: original argument != null
private void printSideways( TreeNode<E> t, int depth )
{
if ( t.getRight() != null )
printSideways( t.getRight(), depth + 1 );

process( t.getValue(), depth );

if ( t.getLeft() != null )
printSideways( t.getLeft(), depth + 1 );
}

// Simply display the toString version of my_data
private void process( E obj, int depth )
{
for ( int j = 1; j <= depth; j++ )
System.out.print( " " );
System.out.println( obj.toString() );
}

// Returns a string representation of the tree rooted at node.
private String toString( TreeNode<E> node )
{
if ( node == null )
return "";
else
return toString( node.getLeft() ) + node.getValue() + ", "
+ toString( node.getRight() );
}

// Implements an Iterator for this tree.
private class MyTreeSetIterator implements Iterator<E>
{
// TODO instance variable(s)

public MyTreeSetIterator( TreeNode<E> root )
{
// TODO complete constructor
}

public boolean hasNext()
{
// TODO complete method
return false; // Fix this!!
}

public E next()
{
// TODO complete method
return null; // Fix this!!
}

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

//************************** main: **************************

public static void main(String[] args)
{
String[] words = {"One", "Two", "Three", "Four", "Five",
"Six", "Seven", "Eight", "Nine", "Ten"};
MyTreeSet bst = new MyTreeSet();

for (String word : words)
{
System.out.println("Added: " + word + " " + bst.add(word));
System.out.println("Contains: " + word + " " + bst.contains(word));
if(bst.add(word))
System.out.println("*** Added a duplicate value ***");
System.out.println(bst);
}
bst.printSideways();

System.out.println("Traversal with an iterator:");
for (Object obj : bst)
System.out.print(obj + " ");
System.out.println();

for (String word : words)
{
System.out.println("Removed: " + word + " " + bst.remove(word));
if(bst.remove(word))
System.out.println("*** Removed a non-existent value ***");
System.out.println(bst);
bst.printSideways();
}
}
}

Figure 23-9 shows a fragment from a simple class that implements a BST. The field root refers to the root of the tree. The no-args constructor creates an empty tree by setting root to null. We have provided the contains, add, remove, and tostring methods. This implementation assumes that the nodes of the tree hold Comparable objects, but it would be easy to provide another constructor that takes a comparator as a parameter. Each of our four methods (contains, add, remove, and tostring) uses a respective private recursive helper method, which takes an additional parameter: the root node of a subtree for which the method is called (Figure 23-10). // Implements a BST with TreeNode nodes. public class MyTreeset \{ private TreeNode root; // holds the root of this BST // Constructor: creates an empty BST. public MyTreeset() \{ // Adds value to the BST rooted at node. Returns the root of the $$//$$ new tree. // Precondition: the tree rooted at node does not contain value. private TreeNode add (TreeNode node, Object value) \{ if (node $$==$$ nul1) node $$=$$ new TreeNode (value); else $$f$$ int diff $$=$$ ((Comparable$$($$ diff $$<0)$$ node. setLeft (add (node.getLeft (), value)); else // if (diff $$>0$$ ) node. setRight (add (node.getright (), value)); j return node; \} $$//$$ Removes value from the BST rooted at node. Returns the root // of the new tree. // Precondition: the tree rooted at node contains value. private TreeNode remove(TreeNode node, Object value) \{ int diff $$=$$ ((Comparable$$==0$$ ) node = removeRoot (node) $$;//$$ base case else if diff $$<0$$ ) node.setLeft (remove (node.getLeft(), value)); else $$//$$ if (diff $$>0$$ ) node.setright (remove (node.getright (), value)); return node; \} Figure 23-10 MyTreeset.java Continued // Returns a string representation of the tree rooted at node. private string tostring(TreeNode node) ( if (node == null) return ""; else return tostring(node.getLeft ()) + node.getvalue () + ", "+ tostring (node.getRight ()); Figure 23-10. Recursive helper methods in $$J_M\backslash Ch23\backslash BST\backslash MyTreeSet.j$$ ava Actually, the contains, add, and remove methods have simple iterative versions as well, because in these methods at each step we either explore the left subtree or the right subtree, but not both. For example: // Iterative version: private boolean contains(TreeNode node, Object value) \{ while (node $$\mathrm{I}=$$ nul1) \{ int diff $$=$$ ((Comparable