Java Question:

I am working on a simple Binary Search Tree class as my homework. I need to write a method where the function returns number of nodes at a given depth. I will provide some images for you guys to understand it more clearly.

Here is the test function to test the code:

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

HERE IS THE TEXT VERSION FOR THOSE WHO WANTS TO COPY/PASTE INTO THEIR COMPILER:

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

*numberOfNodesAtDepth t w *Returns the number of nodes with depthd *Precondition: none aacan: d the depth to search for hint: use a recursive helper function * ToDo 4 public int numNodesAtDepthCint d) return -1; public class simpleBST , Value> t private Node root; 7root of BST static boolean verbose true; I7 set to false to suppress positive test results private class Node private Key key; private Value val; private Node left, right; I/ left and right subtrees // key // associated data 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?C':'C) s.append(key ", val); s.appendCrightnull? '' if (left -null) left.buildString(s); if (right !-null) right.buildString(s); This method is provided to facilitate testing public String toStringO StringBuilder s - new StringBuilderO root.buildString(s); return s.toStringO * Initializes an empty symbol table public simpleBSTO root null; /** size * return the size of the tree public int sizeO return size( root); private int size(Node x) if (x null) return 0; return 1 size(x.left)+size(x.right); testnumNodesAtDepth nacan keys: all substrings of keys of length 1 are added to the ST Racan theDepth: the depth to check for Racan expected: the correct result for this input string and depth public static void testnumNodesAtDepthC String keys, int theDepth, int expected) // create and populate the table from the input string simpleBST