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.