Part One

Here is a program that contains an implementation of a class BinarySearchTree, which corresponds to a binary search tree of integers. This implementation is basically the one we have been discussing in class, and corresponds to Chapter 4 in the textbook. Each node in the binary search tree is a BinaryTreeNode object. Add a size field, of type int , to the BinaryTreeNode class. In the BinarySearchTree implementation, we want the size field of each node object to be set to the size (the number of nodes) of the subtree rooted at the node. Modify the methods involved in the insertion and deletion of elements from the binary search tree so that this is achieved. The modifications should be such that both insert and delete still run time that is proportional to the height of the tree.

Part Two

Add a public method int rangeCount(int x1, int x2) to the BinarySearchTree class. This should return the number of integers stored in the search tree that are strictly greater than x1 but less than x2. For instance, if the binary search tree stores 10, 13, 40, 72, 81, and 95, rangeCount(17, 84) should return 3. The method should run in time proportional to the height of the tree. For this, you will need to exploit the count (I mean size) fields at the nodes of the tree.

You can add code to the main method to test this new method. However, note that Part One will have to be working correctly for such testing.