Write a C++ class called BSTArray with five basic functions for the BST: insert, search, findmin, findmax, and print:

1. int search(x): Find and return the index that stores element x using binary search tree mechanism. Print out all the elements in the search path. You must use the binary tree search algorithm. In other words, do NOT just do a linear search of the array. If the x value is not found, report an error and return -1.

2. int findmax( ): Find and return maximum value in BST. You must use the binary tree search algorithm. In other words, do NOT just perform a linear search of the array. If the tree is empty, return -1.

3. int findmin( ): Find and return minimum value in BST. In other words, do NOT just perform a linear search of the array. If the tree is empty, return -1.

4. void print( ): Print out the BST structure in the form of an array with

index. Specifically, print the index of the array and the value stored at that index starting at zero and ending at the capacity of the array. This is not inorder, preorder, or postorder traversal. In this case, DO use linear array traversal. You may skip printing empty array values.

5. void insert(x): Insert a value element x into BST. Report an error if the value already exists in the tree.

After you finished all functions, implement a driver that makes the following method calls:

insert(5) insert (8) insert (3) insert (1) insert (4) insert (9) insert (18)

insert (20) insert (19) insert (2) Perform print ( ) Perform findmax ( ) and print the return value in your driver Perform findmin( ) and print the return value in your driver Perform search(3) in the BST and print the index that is returned in your driver Perform search(18) in the BST and print the index that is returned in your driver Perform search(19) in the BST and print the index that is returned in your driver

Although the input values are provided, your code should be able to handle random positive input values. Test all edge cases thoroughly.

BSTArray.cpp

#include "BSTArray.h"

BSTArray.h

#pragma once

#include "ElementType.h"

// Create BSTArray class defintiion here

// Remember, your underlying data type will be an array, not a linked list!

// Don't forget class definitions end with a semi-colon!

main.cpp

/*-- main.cpp------------------------------------------------------------This file implements the driver for the BSTArray */

#include BSTArray.h"

#include

using namespace std;

int main()

{

// Create object

// Call methods on object

// Destroy object

}

ElementType.h

#ifndef ELEMENTT

#define ELEMENTT

/*-- ElementType.h ------------------------------------------------------This header file defines the data type being used the an ADT*/

typedef int ElementType;

#endif