public class simpleBST { private Node root; // root of BST static boolean verbose = true; // set to false to suppress positive test results

public class simpleBST, Value> { private Node root; // root of BST

static boolean verbose = true; // set to false to suppress positive test results private class Node { private Key key; // key private Value val; // associated data private Node left, right; // left and right subtrees

public Node(Key key, Value val) { this.key = key; this.val = val; }

/** * this method is provided to facilitate testing */ public void buildString(StringBuilder s) { s.append(left == null ? '[' : '('); s.append(key + "," + val); s.append(right == null ? ']' : ')'); if (left != null) left.buildString(s); if (right != null) right.buildString(s); } } /** * This method is provided to facilitate testing */ public String toString() { StringBuilder s = new StringBuilder(); root.buildString(s); return s.toString(); }

/** * Initializes an empty symbol table. */ public simpleBST() { root = null; }

/** size * * return the size of the tree */ public int size() { return size( root); } private int size(Node x) { if ( x == null) return 0; return 1 + size(x.left)+size(x.right); } /** iokeys * * Returns an Iterable containing the keys of the tree * corresponding to an InOrder traversal * * Hint: follow the approach outlined in class. * use a helper function to carry out the traversal * * * To Do 1 */ public Iterable ioKeys() { Queue qok = new Queue(); // queue of keys return qok; //To do 1 complete this method }

/** put * * Inserts the specified key-value pair into the binary search tree, overwriting the old * value with the new value if the tree already contains the specified key. * * ToDo 2 write a non-recursive implementation of put */ public void put(Key key, Value val) { return; // To Do 2 complete this method }

/** numNodesWithExactlyOneChild * * Returns the number of nodes in the tree * that have exactly one child * * ToDo 3 */ public int numNodesWithExactlyOneChild() { return -1; // ToDo 3 complete this method } /** numberOfNodesAtDepth * * Returns the number of nodes with depth == d * Precondition: none * * param: d the depth to search for * * hint: use a recursive helper function * * ToDo 4 */ public int numNodesAtDepth(int d) { return -1; // ToDo 4 complete this method } /** * * delete * * deletes the key (&value) from the table if the key is present * using the the *dual* of the Hibbard approach from the text. That is, * for the two-child scenario, delete the node by replacing it * with it's predecessor (instead of its successor) * * The functions: max, deleteMax have been provided for you * * ToDo 5: implement a version of delete meeting the above spec * * if you complete this toDo, comment out or delete the print statement, otherwise leave it in. * */ public void delete(Key key) { StdOut.println(" delete not implemented "); return; // ToDo 5 complete this method }

/** max * * return the node in the subtree x with the maximum key ( right most node) * * this is a method to help implement the delete method */ private Node max(Node x) { if ( x.right == null) return x; return max(x.right); }

/** deleteMax * * return the subtree x with the node with maximum key deleted * * this is a method to help implement the delete method */ private Node deleteMax(Node x) { if ( x.right == null) return x.left; x.right = deleteMax(x.right); return x; }