Binary Search Tree Exploration

Implement code to do basic binary search tree manipulations,including insert, traverse, delete, and so on. You may use what the author (Weiss) has in Chapter 4; in fact, be sure to adapt what Weiss has (as closely as you can) for Remove on page 138. Now, Weiss mentions that the code for Remove is inefficient,in that when removing a node with 2 children, it first finds the minimum node in the subtree to the right, then uses Remove to delete that node (which first 'finds' it again). Replace that section with a call to RemoveMin (which you must write) that does the job with just one trip down the tree. Part I: To test your code (on a tree of integers), first insert the values 42 10 74 5 16 100 12 14 15 30 32 in that order. After that, do the following pseudo-code: while the tree is not empty { remove next node (that is, keep a list of the nodes that are left, and delete them one by one) traverse the tree print a line of **************** (so we can keep things separate) } However, make sure that the FIRST node you remove is 10. This is a node with 2 children, which forces RemoveMin to get [login to view URL] of this is to show that your code actually works! Part II: Add a height function, that computes the height of a BST. Now, as we know a binary search tree can behave badly in terms of height; in the worst case it can have height = number of nodes and be just a linked list! Here, we want to explore what is the average height of a randomly generated BST. To this end, generate 100 BST's with 4,096 randomly generated integer values each and print the average height of all 100 trees. Note the following: the usual recursive tree height function will take a LONG time to compute the height of these trees. You should consider an alternative approach for computing the height that will be much faster. Part III: If we insert an array of integers into a BST and then traverse the tree in order, we will have sorted the array. Setup a randomly generated array of 262,144 integers and insert them into a previously empty BST. CPU time this process (see how below). Also sort the array using qsort and time that as well. Print out both elapsed times and label the output. You need not print the sorted array or traverse the tree (but you might do so for yourself prior to turning it in). Note: qsort can be tricky to use correctly if you haven't done it before;(continue on next avaiable window)...... ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request. 3) Complete ownership and distribution copyrights to all work purchased. ## Platform (continue from DESCRIPTION page)look it up and test it out on a small array to make sure you understand it. Note: if you are working under Windows, and you want yourbarray of size 262144 to be local rather than global, you will need to set up a pointer to it and allocate it on the heap; otherwise just put int u[262144]; as global. The problem is that Win32 sets up a default stack of 1 megabyte. So a local declaration of int u[262144] in main() overflows the stack immediately and your program crashes. Another superiority of Linux :-) CPU Timing (for C and C++): You will need to include stdlib.h and time.h to use this. (That's cstdlib and ctime in newer C++ compilers) ... double start, elap; start = clock(); (task to be timed goes here) elap = (clock() - start) / CLOCKS_PER_SEC; Now, elap will be the elapsed time (in seconds) -- I would normally print this out to 2 decimal places. Note: PLEASE WRITE THIS PROGRAM IN C++ . I use the Visual C++ 6.0 to run it ## Deadline information please send the codes ontime