Part One

Enhance our Binary Search Tree class in the following way: add an integer variable called size to the BinaryTreeNode class, as shown here . Then modify the insertion and deletion procedures in the binary search tree class so that for any node x, the variable x.size is always equal to the number of elements in the subtree rooted at x. The modified insertion and deletion procedures should still run in time linear in the height of the tree.

Part Two

Add a method public int rangeCount(int a, int b) to the binary search tree class. This should return the number of integers in the binary search tree that are strictly greater than a and strictly less than b. This method should run in time proportional to the height of the tree as well. To achieve this, you will need to exploit the size fields from part One. We will perhaps discuss the idea needed to do this in class on Monday, Oct 19.

Please submit the two parts in separate files.