This is available as an RTF file. Click here.

Write a class BST_k derived from the class BST to add the one operation of finding the k^th entry in the binary search tree:

#include "BST.h"

class BST_k : public BST
{ public: // You may not change the public portion
   BasePtr Entry_k ( int k );
protected: // You can do anything you want below this
// PROTOTYPE FOR YOUR IMPLEMENTATION FUNCTION
};

You are not allowed to alter the class BST itself — you are just adding a new functionality through the derived class — nor may you change the main program provided to test it. For the class BST, you may either use the restricted implementation available through the 23 April link from the class calendar
      direct link: http://penguin.ewu.edu/class/cscd327/Spr-2002/BST/FirstBST/
or the full implementation available through the 29 April link from the class calendar
      link to 29 April: http://penguin.ewu.edu/class/cscd327/Spr-2002/04/29/
— the main program to test your implementation only uses the restricted set of behaviors.

If "k" is negative or if the BST contains fewer than (k+1) entries, Entry_k should return a NULL pointer. Otherwise it should return a pointer to the requested entry, where counting starts at zero. Thus the smallest entry in the BST is the zeroeth, while the largest entry in a BST of size N is in position (N–1).

25-point option: implement something like
   void Entry_k ( BasePtr Node, int k, int &Current, BasePtr &RtnVal );
where the public: function would look like this:
   BasePtr BST_k::Entry_k ( int k )
   {  BasePtr N = NULL; int Current = 0;
      Entry_k ( Root, k, Current, N );
      return N;
   }
"Node" is the node currently being processed; "k" is passed along; "Current" identifies how many entries have been visited in the in-order position, and "RtnVal" is the reference parameter that is set to point at the k^th entry — and remains NULL if no such entry is found. Hint: the in-order position of the traversal might well have something like the following code segment:
   if (k == Current++) RtnVal = Node;

30-point option: implement the protected function as BasePtr Entry_k(...) where your protected function does a traversal, but then itself returns the appropriate pointer. The parameter list of the protected function is up to you. Note for hair-splitters: it is not sufficient for the extra points to simply implement the 25-point option and then insert an extra protected function that calls it.  [Note: if an extra-credit submission is not fully correct, the partial credit will be based on a maximum of 25 points.]

35-point option: implement the protected function as BasePtr Entry_k(...) where your protected function takes advantage of the Size field in the struct BaseCell and moves directly to the k^th entry without traversing the BST up to that point.  [Note: if an extra-credit submission is not fully correct, the partial credit will be based on a maximum of 25 points.]