package CSC301SP18Homework; // change the package if you want

import stdlib.StdOut;

* The B(inary)S(earch)T(ree) class represents a symbol table of

* generic key-value pairs. It supports put, get, and delete methods.

* The book's recursive versions of get and put have been renamed

* rGet and rPut

* to facilitate testing of your non-recursive versions

*

*/

public class BST301, Value> {

private Node root; // root of BST

static boolean verbose = false; // set to false to mute "correct" test output messages

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;

}

/**

* Appends the preorder string representation of the sub-tree to the given StringBuilder.

*/

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

}

}

/**

* Returns the preorder string representation of the BST.

*/

public String toString() {

StringBuilder s = new StringBuilder();

root.buildString(s);

return s.toString();

}

/**

* Initializes an empty symbol table.

*/

public BST301() {

}

/** size

*

* return the size of the tree

*/

public int size() {

return size(root);

// ToDo 0

}

public int size(Node node) {

if (node==null) return 0;

else return 1+size(node.left)+size(node.right);

}

10. Write an instance method, numNodesWithOneCh ild, to determine the number of nodes in a BST301 that have exactly one child. Example: BST301 tree10; // assume tree10 gets created somehow int answer- tree10.numNodesWithOneChild) 11. Write an instance method, numNodes DeeperThan, to determine the number of nodes that are at depth greater than some value ( passed as a parameter) Example: BST301 treelli // assume treell gets created somehow int answer-tree11.numNodes DeeperThan (6)