// Implements a BST with TreeNode nodes

import java.util.Stack;

import java.util.Iterator;

import java.util.NoSuchElementException;

@SuppressWarnings("unchecked")

// Normally, TreeNode and MyTreeSet would be "generic" (type-specific)

// classes and hold Comparable objects, but this is beyond the scope of

// the Java Methods book. Without @SuppressWarnings, this class would give

// three "Unchecked cast" warnings.

public class MyTreeSet implements Iterable

{

//instance field for the root

private TreeNode root;

//constructor to create an empty BST

// Returns true if value has been added; otherwise returns false.

public boolean add(Object value)

{

root = add(root, value);

return true;

}

// These 3 methods each return a different string representation of this BST.

public String toString()

{

return "[" + toString(root) + "]";

}

public String printPre()

{

return "[" + printPre(root) + "]";

}

public String printPost()

{

return "[" + printPost(root) + "]";

}

// Returns an iterator for this BST.

public Iterator

{

return new MyTreeSetIterator(root);

}

//*************************************************************

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

//*************************************************************

// 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)

{ //you'll code this method, using recursion.

return null;

}

// Returns a string representation of the tree rooted at node, in the inOrder traversal.

private String toString(TreeNode node)

{

//you'll code this, using recursion

return null;

}

// Returns a string representation of the tree rooted at node, in the PostOrder traversal.

private String printPost(TreeNode node)

{

//you'll code this, using recursion

return null;

}

// Returns a string representation of the tree rooted at node, in the PreOrder traversal.

private String printPre(TreeNode node)

{

//you'll code this, using recursion

return null;

}

//**************************************

// Implements an Iterator for this tree.

//****************************************

private class MyTreeSetIterator implements Iterator

{

private Stack stk;

public MyTreeSetIterator(TreeNode root)

{

stk = new Stack();

TreeNode node = root;

while (node != null)

{

stk.push(node);

node = node.getLeft();

}

}

public boolean hasNext()

{

return !stk.isEmpty();

}

public Object next()

{

if (stk.isEmpty())

throw new NoSuchElementException();

TreeNode node = stk.pop();

Object obj = node.getValue();

node = node.getRight();

while (node != null)

{

stk.push(node);

node = node.getLeft();

}

return obj;

}

public void remove()

{

throw new UnsupportedOperationException();

}

}

}

Directions - This program demonstrates the adding of nodes into a Binary Search Tree, and then the printing of them using inOrder, postOrder, and preOrder Traversal. The TreeNode and MyTree Set Classes have been provided on repl.it. As you will see, recursive solutions are both elegant and simple and you are encouraged to use recursion whenever possible when working with trees. MyTree Set Class: 1. Constructor - set the root instance field such that it's an empty tree. 2. Add helper method (line 58) - a. Use the compare To method** to decide if your node needs to go left or right of the root, and then call either setLeft() or setRight() (from the TreeNode class). Since we don't know if the node could be placed immediately, have setLeft() or setRight() call the add method by passing a call to the add method as your parameter for setLeft() or setRight(). This is a little different than the recursive methods we've used lately, which just returned the recursive call. Here's the general idea: 1. Check for the base case 2. If not the base case, a. if newNode needs to go on the left, call setLeft(), passing it a recursive call to this add method. b. else, call setRight(), passing it a recursive call to this add method 3. Return the node ** Compare To method hint - Since we need to compare the node with the parameter "value which is of the generic type Object, you need to cast that field to a Comparable