Number of nodes at depth please

/** * 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) { Node x = new Node(key, val); if (root == null) { root = x; return; } Node parent = null; Node y = root; while(y != null) { parent = y; int res = key.compareTo(y.key); if(res < 0) y = y.left; else if(res > 0) y = y.right; else { y.val = val; return; } } int res = key.compareTo(parent.key); if(res < 0) parent.left = x; else parent.right = x; } /** numNodesWithExactlyOneChild * * Returns the number of nodes in the tree * that have exactly one child * * ToDo 3 */ public int numNodesWithExactlyOneChild() { Queue q = new Queue(); q.enqueue(root); int count = 0; while (!q.isEmpty()) { Node temp = q.dequeue(); if (temp.left!=null && temp.right==null || temp.left==null && temp.right!=null) count++; if (temp.left != null) q.enqueue(temp.left); if (temp.right != null) q.enqueue(temp.right); } return count; } /** 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) { //write get depth function //check if each Node has this depth //return count // to start - return depth of node here, then check against d and return return -1; // ToDo 4 complete this method }