At the end of this work you should submit a header file BinarySearchTree.h with class interfaces and function declarations and BinarySearchTree.cpp that includes all the implementations.

Do not submit a main routine!

You are to write three separate classes that belong to a namespace pic10b. You should be writing a Tree class, as the binary search tree data structure that will store double values; a node class, to store the data in nodes where each node tracks its left/right child nodes as well as its parent node; and an iterator class to traverse the tree.

The node and iterator classes should be nested inside of the Tree class.

The code must be free of memory leaks; when a Tree is destroyed or assigned-to, the managed memory must be freed. The precise manner you implement these classes could vary but at the very least you must adhere to the requirements below and ensure that your code has the same behaviour as the example shown.

Tree must:

• have a default constructor creating a tree storing nothing;

• have a destructor;

• have copy and move constructors;

• have copy and move assignment operators;

• have a swap function (visible at the pic10b namespace level) to swap two Trees;

• have an insert member function accepting a double value and adding it to the tree;

• have an erase member function accepting an iterator and removing the node managed by the iterator from the tree;

• have begin and end member functions returning an iterator to the first node and an iterator one past the final node, respectively;

• have a size member function returning the number of elements in the Tree;

• have a find member function returning the iterator to the node with a given value if found and otherwise returning the past-the-end iterator.

• iterator must:

  overload the prefix and postfix version of ++; overload the prefix and postfix version of - -; overload == and != as comparison operators; and overload the dereferencing operator.

• An example of the desired output for the code below is provided. Note that due to the random numbers involved, your runs of the program will not generate the identical output.

• #include "BinarySearchTree.h" #include #include int main(){ std::srand(static_cast(std::time(nullptr))); // seed pic10b::Tree t1; // empty tree for (size_t i = 0; i (std::rand()) / RAND_MAX); } std::cout > low >> up; // read in values auto itr = t1.begin(); while (itr != t1.end()){ // while not at the end if ((low  

• 
• zoom in on the picture!

• Some initial guidance to get you on your way...

• Be sure to draw diagrams!

• Get the insert and size functions working first; then worry about traversing the tree with iterators. After that, you can worry about other features like erase and copy constructors, destructors, etc.

• The insertNode function for node can return a bool, depending on whether the node gets inserted (recall duplicates are not allowed). Depending on that value, the size counter can go up or stay the same. Be sure that the insertNode function returns something regardless of whether a node was actually inserted...

• The destruction process, like the copy process, can be done recursively: from the perspective of a node, destroy all nodes to the left then all nodes to the right and then self-destruct!

• The find function is a member of Tree and the tree is structured perfectly for binary search. Just start at the root and move left/right until the value is found or there are no more nodes to search through.

Thank you! It's in C++

Elements: 0.028779 0.129337 0.151555 0.28254 0.282937 0.507645 0.579516 0.71865 0.749962 0.960845 Last element is: .960845 ount of elements: 10 nter lower and upper values for removal: .15 0.55 t1 and t2 elements 0.028779 0.129337 0.579516 0.71865 0.749962 .960845 D.028779 0.129337 0.151555 0.28254 0.282937 0.507645 0.579516 0.71865 0.749962 0 960845 t2 size now: 0 3.14 first item! Elements: 0.028779 0.129337 0.151555 0.28254 0.282937 0.507645 0.579516 0.71865 0.749962 0.960845 Last element is: .960845 ount of elements: 10 nter lower and upper values for removal: .15 0.55 t1 and t2 elements 0.028779 0.129337 0.579516 0.71865 0.749962 .960845 D.028779 0.129337 0.151555 0.28254 0.282937 0.507645 0.579516 0.71865 0.749962 0 960845 t2 size now: 0 3.14 first item