Do not use any pointers.

Executive Summary: A binary search tree is a binary tree in which every node satisfies the following: ? the key of every node in the left subtree is smaller than the key of this node ? the key of every node in the right subtree is larger than the key of this node It is possible to construct BST with pointers. A single dimension array is also good enough to construct a BST. One example is like following:

Staring with array index 1 For any node, to find its parents index: If the nodes index is even number --- index/2 If the nodes index is odd number --- (index-1)/2 For any node, to find its left side childs index --- index*2 For any node, to find its right side childs index --- index*2 + 1

Project Objective: in completing this project, you will ? Understand the details of BST, including search, insert, delete, find max, find min ? Familiar with the links between array and BST

Detailed Specification: Write six basic functions for the BST: Insert, Delete, Search, Find_max, Find_min, and Print_BST 1. Search(x): Find out the index that stores element x using binary search tree mechanism. Print out all the elements in the search path. 2. Find_max( ): Find and print maximum value in BST 3. Find_min( ): Find and print minimum value in BST 4. Print_BST( ): Print out the BST structure in the form of array with index. 5. Insert(x): Insert a value element x into BST 6. (BOUNS) Delete(x): Delete element x in BST including ALL 3 situations we discussed

After you finished the all functions, following are the things you need to carry out: 1. Insert(5) 2. Insert(8) 3. Insert(3) 4. Insert(1) 5. Insert(4) 6. Insert(9) 7. Insert(18) 8. Insert(20) 9. Insert(19) 10. Insert(2) 11. Perform Print_BST( ) 12. Perform Find_max( ) 13. Perform Find_min( ) 14. Perform Search(3) in the BST 15. Perform Search(18) in the BST 16. Perform Search(19) in the BST 17. Delete(19) in the BST, perform Print_BST( ) (BOUNS) 18. Delete(2) in the BST, perform Print_BST( ) (BOUNS) 19. Delete(8) in the BST, perform Print_BST( ) (BOUNS) 20. Delete(3) in the BST, perform Print_BST( ) (BOUNS) 21. Delete(5) in the BST, perform Print_BST( ) (BOUNS) (p.s. Although the input values are provided, your code should be able to handle random input values.)

Do not use any pointers.