Task 1. Defining a class,

BSTNode Start this task by designing the BSTNode class for the BST. For the initial development you should just build the node to hold a std::string as its data. The BSTNode class will consist of a string and left and right pointers. It will initialize the node using its constructor. You will also overload the stream insertion operator << to output a node. Will you need access and/or modify the contents of the nodes from outside the node? Yes! Then you should implement getters/setters. Note: you will be inserting data into the tree using recursion. How will this impact your getters in the BSTNode class? Consider passing the left and right pointers back by reference. The data in the node is a std::string, should we pass the newData value into the setter using pass-by-reference? Recall, a std::string is an object type, and hence, if the object is not passed by reference, then a copy of the object is made (std::string copy constructor is invoked). Is this the intent? Probably not!

Task 2. Now create the BST class Implement a BST class.

You are now ready to define the BST class. You should create an attribute member for a pointer that will be the root of the BST. The pointers should be of type BSTNode. You will also implement the constructor, the deep copy constructor, and the destructor (should destroy the tree through postorder traversing of nodes). Additionally, you need: insertNode ( ) - that adds an item to the BST. Recall the properties of a BST. The values in any left subtree are less than its parent node, and any values in the right subtree are greater than its parent node. Use recursion in your implementation! inOrderTraversal ( ) - that prints the contents of the BST inorder. Use recursion in your implementation! preOrderTraversal ( ) - that prints the contents of the BST preorder. Use recursion in your implementation! postOrderTraversal ( ) - that prints the contents of the BST postorder. Use recursion in your implementation! isEmpty ( ) - that is a Boolean function that indicates that the BST is empty or not. You will overload the stream insertion operator << to output a BST in an elegant way. NOTE: Listed below are the algorithms for the traversals.

In-Order Traversal: 1. Traverse the left subtree by recursively calling inOrderTraversal() 2. Access the data of the current node 3. Traverse the right subtree by recursively calling inOrderTraversal() Pre-Order Traversal: 1. Access the data of the current node 2. Traverse the left subtree by recursively calling preOrderTraversal() 3. Traverse the right subtree by recursively calling preOrderTraversal() Post-Order Traversal: 1. Traverse the left subtree by recursively calling postOrderTraversal() 2. Traverse the right subtree by recursively calling postOrderTraversal() 3. Access the data of the current node Lets say we have the following

BST: 42 / \ 25 75 / \ / \ 10 30 65 100 / \ / \ / \ / \ 15 70 The in-order traversal would print: 10 15 25 30 42 65 70 75 100 The pre-order traversal would print: 42 25 10 15 30 75 65 70 100 The post-order traversal would print: 15 10 30 25 70 65 100 75 42 // The value in each node is not printed until the values of its children are printed