JAVA QUESTION:

*******THE QUESTION:********

/** 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; }

**********USEFUL CODE FROM THE ASSIGNMENT:***********

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); }

******TEST CODES:*******

public static void testnumNodesAtDepth( String keys, int theDepth, int expected ) {

// create and populate the table from the input string simpleBST aTree = from(keys,keys); // do the test int actual = aTree.numNodesAtDepth(theDepth);

if ( actual == expected) {// test passes if (verbose) StdOut.format("testnumNodesAtDepthD: Correct Keys: [ %s ] actual: %d ", keys, actual); } else StdOut.format("testnumNodesAtDepthD: *Error* Keys: [ %s ] expected: %d actual: %d ", keys, expected, actual); }

public static void numNodesAtDepthDTests() { testnumNodesAtDepth("",0, 0); // empty tree has no nodes at any depth testnumNodesAtDepth("C",0, 1); testnumNodesAtDepth("BAC",0, 1); testnumNodesAtDepth("ABCDEFG",3, 1); testnumNodesAtDepth("DBACFEG",1, 2); testnumNodesAtDepth("DBACFEG",2, 4); testnumNodesAtDepth("DBACFEG",3, 0); testnumNodesAtDepth("EAIDFBHCG",4, 2);

StdOut.println("----------- numNodesAtDepthD tests completed"); }