•  default constructor
• get_root
• insert (and its helper function insert_value)
• is_empty

• We are going to build this header file piece-by-piece.
• Here is our bare-bones header file for the work we are going to do on our BST today.
• We will add public functions and private helper functions as we go along.
• Take a moment to familiarize yourself with this class.
• How is the node being represented?
• What kind of data does this BST hold?
• What are the private fields of the BST?
  

#ifndef BST_H_
#define BST_H_

#include <cstddef>
#include <string>

using namespace std;

template <class bstdata>
class BST
{
    private:
        struct Node
        {
                bstdata data;
                Node* left;
                Node* right;

                Node(): left(NULL), right(NULL){}
                Node(bstdata newdata): left(NULL), right(NULL), data(newdata){}
        };

        typedef struct Node* Nodeptr;

        Nodeptr root;
       

                    /**Private helper functions*/

        void insert_value(Nodeptr root, bstdata value);

        //private helper function for insert

        //recursively inserts a value into the BST

        void inOrderPrint(Nodeptr root);

        //private helper function for inOrderPrint

        //recursively prints tree values in order from smallest to largest

        void preOrderPrint(Nodeptr root);

        //private helper function for preOrderPrint

        //recursively prints tree values in preorder

        void postOrderPrint(Nodeptr root);

        //private helper function for postOrderPrint

        //recursively prints tree values according in postorder

    public:
        BST();

        //Instantiates a new BST

        //post: a new BST object

        bool is_empty();

        //determines whether the BST is empty

        void insert(bstdata value);

        //inserts a new value into the BST

        //post: a new value inserted into the BST

        bstdata getRoot();

        //returns the value stored at the root of the BST

        //pre: the BST is not empty

        void inOrderPrint();

        //calls the inOrderPrint function to print out the values

        //stored in the BST

        void preOrderPrint();

        //calls the reOrderPrint function to print out the values

        //stored in the BST

       
        void postOrderPrint();

        //calls the postOrderPrint function to print out the values

        //stored in the BST

        //more functions to be added here!

};

BST Functions: Insert

• As always, the best functions to write first are your default constructor, an add function and a print function.
• We have the default constructor, let's write our add function next.
• The functions you will be writing for the BST will take advantage of the recursive structure of the BST.
• Let's look at how this would work for insertion.
• Imagine that we are trying to insert 4 into our BST as in the image below.
  
• At each root node of a subtree, we need to make a decision. Do we go left? Do we go right? Or if the root node is null, do we insert right we should add right where we are.
  

Image source.

• Thus, our process is recursive as we are making the same decision at each node.
• Our BST users do not have direct access to any of the nodes in the BST or their data or links.
• Therefore, we need to call a private helper function inside of insert and pass the root node to this function.
• The private helper function is the recursive function that is going to do most of the work here.
• The private helper function is called insert_value and it takes the root and a value as parameters.
• The public wrapper function is called insert and it simply takes a value.
• Here is the code for the public wrapper function:

template <class bstdata>
void BST<bstdata>::insert(bstdata value)
{
    if (root == NULL)

    {
        root = new Node(value); //if the tree is empty insert the value at the root

    }
    else
        insert_value(root, value); //otherwise call the helper function, passing it the root

}

• Here is the pseudocode for the private helper function:

Pseudocode for insert_value(root, value) function

1. Base Case: the value to insert is equal to the data stored at the root

If this is true, return

2. Check if the value to insert is smaller than the data stored at the root.

2a. If this is true

2aa. Check if root left is NULL

2aaa. If this is true, insert the value at root left

2b. If the root left is not NULL

2bb.recursively call the insert_value function passing it root left and value

3. Otherwise

3a. Check if the root right is NULL

3aa. If this is true, insert the value at root right

3b. If the root right is not NULL

3bb. recursively call the insert_value function passing it root right and value

• Next, create a new file called BSTTest.cpp.
• This file will be your test file.
• In this file add a main function and include your BST.h
• Inside of main, create a new BST of integers.
• Try adding a value to it by calling the add function.
• Then, call the getRoot function to print out the root of your tree, like so:

cout << "Root of tree: " << bst.getRoot() << endl;

• Once everything seems to be working okay you can move on to the next functions.

Part 2: Tree Traversals

• Now, we are going to add what are called "Tree Traversals" to our BST data structure.
• We are going to add them as printing functions to allow us to print out the data in our BST.
• To help you understand these concepts, I recommend that you watch this video on tree traversals.
  

inOrderPrint()

• Because a BST is not a linear structure, there are multiple approaches that we can take to printing out its contents.
• Look at the example below and you will see that there are various printing options.
  

• One of these is to do what we call "Printing In Order."
• InOrderPrint will print the values from smallest to largest.
• So, for the tree above, it would print the values as: 1 3 4 6 7 8 10 13 14
• Again, this is a recursive process, which goes left root right
  
• The pseudocode for inOrderPrint is as follows:

Pseudocode for inOrderPrint(root)

1. If the root is not NULL

a. Call inOrderPrint recursively on the root left.

b. Print the data at the root

c. Call inOrderPrint recursively on the root right

• Implement the above function in your code and then test it by adding some new data to your BST and then call preOrderPrint on your BST object.

Add preOrderPrint and postOrderPrint

• Once again, BSTs are not linear structures, so there are many "orderings" in which we could print out the data contained in the nodes.
• We saw the recursive inOrderPrint above
• You are now going to write preOrderPrint and postOrderPrint and their helper functions.
• These functions are also recursive.
• Below is the pseudocode for these two functions.
• Note the similarities and differences between these functions and inOrderPrint.
• When does the inOrder print call cout compared to preOrderPrint and postOrderPrint?
  

• Submit your BST.h and your BSTTest.cpp, including ALL of the tests you ran on your code.
  
• Note that you should have 11 functions in total - 7 functions + 4 helper functions.
• You should also have tests for each of the 7 functions in your BSTTest.cpp
  

• You will receive 7 points per function and 23 points for fully testing your functions (each function should be called at least twice).