Implement a Binary Search Tree template based on the starter code provided. BST must be able

to handle different types of data.

You must implement all the public functions in the starter code. You can implement private

functions as needed.

The file bst_test.cpp is provided for basic testing. You should extend the tests and make

sure all functions in BST are tested using assert statements.

The following main is provided, so you can confirm how functions are called and what the

expected output is. You must use the CATCH framework to fully test your program.

The goal of this assignment is to develop a deep understanding of binary search trees and

continue practicing memory management.

Write one function at a time. Test it before moving on to the next function. I suggest starting

with Add and XTraverse functions. Use valgrind to check for memory leaks as you develop

the program. Much easier to fix things early on.

Additional Requirements

4. Program compiles without warnings or errors with the following flags

-Wall -Wextra -Wno-sign-compare

5. Any warnings from cpplint or cppcheck should be fixed or explained in Readme file.

6. valgrind should not report any memory as "definitely lost"

bst.hpp

/** * Binary Search Tree - Template * * Store values in a BST * Can use Inorder, Preorder and Postorder to traverse tree * Can use Add/Remove to modify tree * Rebalance creates a balanced tree * * @author XXX * @date XXX */ #ifndef BST_HPP #define BST_HPP #include  #include  using namespace std; template class BST { // display a sideways ascii representation of tree friend ostream &operator<<(ostream &os, const BST &bst) { bst.sideways(bst.rootPtr, 0, os); return os; } private: // Node for BST typedef struct node { T data; struct node *leftPtr; struct node *rightPtr; } Node; // root of the tree Node *rootPtr{nullptr}; // Make a new BST Node Node *makeNode(const T &value) const { // TODO(me) return nullptr; } // helper function for displaying tree sideways, works recursively void sideways(Node *current, int level, ostream &os) const { static const string indents{" "}; if (current) { level++; sideways(current->rightPtr, level, os); // indent for readability, 4 spaces per depth level for (int i = level; i >= 0; i--) os << indents; // display information of object os << current->data << endl; sideways(current->leftPtr, level, os); } } // Additional private functions // TODO(me) public: // constructor, empty tree BST() { // TODO(me) } // constructor, tree with root explicit BST(const T &rootItem) { // TODO(me) } // given an array of length n // create a tree to have all items in that array // with the minimum height (i.e. rebalance) BST(const T arr[], int n) { // TODO(me) } // copy constructor BST(const BST &bst) { // TODO(me) } // destructor virtual ~BST() { // TODO(me) } // true if no nodes in BST bool IsEmpty() const { // TODO(me) return true; } // 0 if empty, 1 if only root, otherwise // height of root is max height of subtrees + 1 int getHeight() const { // TODO(me) return 0; } // number of nodes in BST int NumberOfNodes() const { // TODO(me) return 0; } // add a new item, return true if successful bool Add(const T &item) { // TODO(me) return true; } // remove item, return true if successful bool Remove(const T &item) { // TODO(me) return true; } // true if item is in BST bool Contains(const T &item) const { // TODO(me) return true; } // inorder traversal: left-root-right // takes a function that takes a single parameter of type T void InorderTraverse(void visit(const T &item)) const { // TODO(me) } // preorder traversal: root-left-right void PreorderTraverse(void visit(const T &item)) const { // TODO(me) } // postorder traversal: left-right-root void PostorderTraverse(void visit(const T &item)) const { // TODO(me) } // create dynamic array, copy all the items to the array // and then read the array to re-create this tree from scratch // so that resulting tree should be balanced void Rebalance() { // TODO(me) } // delete all nodes in tree void Clear() { // TODO(me) } // trees are equal if they have the same structure // AND the same item values at all the nodes bool operator==(const BST &other) const { // TODO(me) return true; } // not == to each other bool operator!=(const BST &other) const { // TODO(me) return true; } }; #endif // BST_HPP

bst_test.cpp

/** * Testing BST - Binary Search Tree functions * * @author Yusuf Pisan * @date 19 Jan 2019 */ #include  #include  #include  #include  #include "bst.hpp" using namespace std; /** * Trying to avoid global variables, * by creating a singleton class with our visitor functions * stringstream SS contains the output from visitor */ class TreeVisitor { public: TreeVisitor() = delete; // insert output to SS rather than cout, so we can test it static stringstream SS; static string GetSS() { return SS.str(); } static void ResetSS() { SS.str(string()); } // instead of cout, insert item into a string stream static void visitor(const string &item) { SS << item; } // instead of cout, insert item into a string stream static void visitor(const int &item) { SS << item; } }; // initialize the static variable stringstream TreeVisitor::SS; void testBSTConstructors() { cout << " * Testing 0 param constructor, ==, !=, IsEmpty, and XTraverse" << endl; BST b1; BST b2; BST b3; // == and != for empty trees assert(b1 == b2 && (!(b1 != b2))); b1.Add("c"); b2.Add("c"); b3.Add("b"); // == and !- for 1-node trees b1, b2, b3 assert(b1 == b2 && (!(b1 != b2))); assert(b1 != b3 && (!(b1 == b3))); b1.Add("a"); b1.Add("f"); b1.Add("g"); b1.Add("x"); b2.Add("a"); b2.Add("f"); b2.Add("g"); b2.Add("x"); // == for 5-node trees b1, b2 assert(b1 == b2 && (!(b1 != b2))); BST b4(b3); // copy constructor for 1-node trees b3, b4 assert(b3 == b4 && (!(b3 != b4))); BST b5(b1); // copy constructor for 5-node trees b1, b5 assert(b1 == b5 && (!(b5 != b1))); BST b7("b"); // 1-param constructor for 1-node trees b3, b7 assert(b3 == b7 && (!(b3 != b7))); cout << "b1 is: " << endl; cout << b1 << endl; TreeVisitor::ResetSS(); b1.InorderTraverse(TreeVisitor::visitor); string result = "acfgx"; assert(TreeVisitor::GetSS() == result); TreeVisitor::ResetSS(); b1.PreorderTraverse(TreeVisitor::visitor); result = "cafgx"; assert(TreeVisitor::GetSS() == result); TreeVisitor::ResetSS(); b1.PostorderTraverse(TreeVisitor::visitor); result = "axgfc"; assert(TreeVisitor::GetSS() == result); cout << "Done testBSTConstructors" << endl; } void testBSTAll() { testBSTConstructors(); }

main.cpp

/** * Driver for starting BST tests */ // some interactive and non-interactive testes to test BST #include  using namespace std; // forward declaration, implementation in bst_test.cpp void testBSTAll(); int main() { testBSTAll(); cout << "Done!" << endl; return 0; }