/** * The simpleBST class represents a symbol table of * generic key-value pairs using a binary search tree. * recursive versions of get and put have been renamed * rGet and rPut to facilitate testing of your non-recursive versions * you may not use rPut or rGet as part of your 'toDo' solutions * a size method is also provided which you may use * */ 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 if(root != null) ioKeyHelper(root, qok); return qok; //To do 1 } public void ioKeyHelper(Node x, Queue q) { if(x.left != null) ioKeyHelper(x.left, q); q.enqueue(x.key); if(x.right != null) ioKeyHelper(x.right, q); } /** 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 }