In C++. Thanks.

In this program you will be writing a very simple and incomplete version of the Binary Search Tree data structure. It is incomplete, because we will only be writing 3 functions for the class. Here is the Tree class definition from Tree.h, you will need to write the 3 member functions for the Tree class (insert, op << and print):

// Tree class definition from Tree.h class Tree { public: class Node { public: Node() : left(nullptr), right(nullptr), data(0){} Node(int val) : left(nullptr), right(nullptr), data(val) {} int data; Node *left, *right; }; Tree() : count(0), root(nullptr) {} bool insert(int newVal); friend ostream& operator << (ostream& str, const Tree& tree); // calls print and // outputs count private: void print(ostream& ostr, Node* curNode) const; // recursive function Node* root; int count; };

Requirements:

- The insert member function should use loops to find the correct place for the new data, and the print function must use recursion to print out the sorted data from the Tree.

- Inside the insert function you NEED to give the following debug output:

• insert in empty tree when this is the case
• checking left/right when moving to the left or right down tree
• inserting TRUE/FALSE able to insert or not {for an example look at the Program 6 Notes Tree.pdf in the Lecture section on Canvas}

- Insert the following numbers into the tree in this order:

6 9 3 5 5 7 2 10 4 1 8

....and then output the data in sorted order and count from the list