Lab BSTA - Binary Search Tree implemented with static array

The partial source code for this lab is at http://vpl.ccom.uprp.edu.

You are provided with the declaration of a template class BSTA that will implement a Binary Search Tree using a static array. The root of the array will be at index 1. You can assume that BST will only store unique elements (no duplicates). Notice the data members are:

• A, a static array of size CAPACITY.
• valid, a static array of size CAPACITY that will be used to keep track which indices of the array A are actual nodes of the BST. For instance, Figure 1 illustrates the state of A and valid for a tree.

Figure 1. A BST and the state of its array implementation

Implement the following member functions:

• the constructor
• bool search(const T& e) const: returns true if found, false otherwise. Use an O(logn) algorithm.
• bool insert(const T& e): returns true if the element was inserted, false otherwise. Use an O(logn) algorithm.
• bool remove(const T& e): returns true if the element was removed, false otherwise. Use an O(logn) algorithm.
• int leafQty() const : returns the number of leaves in the tree. For example, the tree in Figure 1 contains 3 leaves.

The operator<< is currently overloaded for you to display a sideways representation of the graph. For example, if d is a BSTA that contains the elements in Figure 1. Then cout << d displays:

        10
    9
        8
7
        0
    -3

You are also provided a client that accepts the following commands and invokes the corresponding functions:

• i integer : inserts the integer into the BST (by invoking the insert() member function). Prints whether the insertion was successful or not.
• r integer : removes the integer from the BST (by invoking the insert() member function). Prints whether the remove was successful or not.
• d : displays the BST
• s integer: searches the integer in the BST. Prints the result.

Your task is to implement the member functions of the BSTA class. You may add other public and private member (helper) functions. Do not modify the client.

You are given input files (input1.txt through input3.txt) that contain the inputs that will be provided to your program as part of the autograding. Output files (output1.txt through output3.txt) contain the expected results.