Please solve this problem with C++ with .cpp and .h fileand show every step clearly.

//main #include #include "BinarySearchTree.h" #include using namespace std;

int main() {

TreeType x;

x.InsertItem(10); x.InsertItem(5); x.InsertItem(2); x.InsertItem(7); x.InsertItem(15); x.InsertItem(12); x.InsertItem(20);

x.ResetTree(IN_ORDER);

int out=0; while(x.GetNextItem(out,IN_ORDER)){ cout

cout

/*while(!x.inQue.IsEmpty()){ cout

if(!x.DeleteItem(0)) cout

cout

x.ResetTree(IN_ORDER);

out=0; while(x.GetNextItem(out,IN_ORDER)){ cout

if(x.RetrieveItem(out)){ cout

x.MakeEmpty(); if(x.IsEmpty()){ cout

cout

return 0; }

//BinarySearchTree.tpp #include "BinarySearchTree.h" #include

using namespace std; template TreeType::TreeType() { root = nullptr; }

template void Destroy(TreeNode*& tree) { if (tree != nullptr) { Destroy(tree->left); Destroy(tree->right); delete tree; tree = nullptr; } }

template TreeType::~TreeType() { Destroy(root); }

template void TreeType::MakeEmpty() { Destroy(root); }

template bool TreeType::IsEmpty() { return (root == nullptr); }

template bool TreeType::IsFull() { TreeNode* location; try { location = new TreeNode; delete location; return false; } catch(bad_alloc& exception) { return true; } }

template int CountNodes(TreeNode* tree) { if (tree == nullptr) return 0; else return CountNodes(tree->left) + CountNodes(tree->right) + 1; }

template int TreeType::LengthIs() { return CountNodes(root); }

template void Retrieve(TreeNode* tree, ItemType& item, bool& found) { if (tree == nullptr) found = false; else if (item info) Retrieve(tree->left, item, found); else if (item > tree->info) Retrieve(tree->right, item, found); else { item = tree->info; found = true; } }

template bool TreeType::RetrieveItem(ItemType& item) { bool found; Retrieve(root, item, found); return found; }

template void Insert(TreeNode*& tree, ItemType item) { // reference of a treenode pointer variable if (tree == nullptr) { tree = new TreeNode; tree->right = nullptr; tree->left = nullptr; tree->info = item; } else if (item info) Insert(tree->left, item); else Insert(tree->right, item); }

template bool TreeType::InsertItem(ItemType item) { if(IsFull()){ return false; } Insert(root, item); return true; }

template void GetPredecessor(TreeNode* tree, ItemType& data) { while (tree->right != nullptr) tree = tree->right; data = tree->info; }

template void DeleteNode(TreeNode*& tree) { TreeNode* tempPtr; tempPtr = tree; if (tree->left == nullptr) { tree = tree->right; delete tempPtr; } else if (tree->right == nullptr) { tree = tree->left; delete tempPtr; } else { ItemType data; GetPredecessor(tree->left, data); tree->info = data; Delete(tree->left, data); } }

template bool Delete(TreeNode*& tree, ItemType item) { if (tree == nullptr) return false; if (item info) return Delete(tree->left, item); else if (item > tree->info) return Delete(tree->right, item); else { DeleteNode(tree); return true; } }

template bool TreeType::DeleteItem(ItemType item) { return Delete(root, item); }

template void PreOrder(TreeNode* tree, Queue& Que) { if (tree != nullptr) { Que.EnQueue(tree->info); PreOrder(tree->left, Que); PreOrder(tree->right, Que); } }

template void InOrder(TreeNode* tree, Queue& Que) { if (tree != nullptr) { InOrder(tree->left, Que); Que.EnQueue(tree->info); InOrder(tree->right, Que); } }

template void PostOrder(TreeNode* tree, Queue& Que) { if (tree != nullptr) { PostOrder(tree->left, Que); PostOrder(tree->right, Que); Que.EnQueue(tree->info); } }

template void TreeType::ResetTree(OrderType order) { switch (order) { case PRE_ORDER: preQue.MakeEmpty(); PreOrder(root, preQue); break; case IN_ORDER: inQue.MakeEmpty(); InOrder(root, inQue); break; case POST_ORDER: postQue.MakeEmpty(); PostOrder(root, postQue); break; } }

template bool TreeType::GetNextItem(ItemType& item, OrderType order) { switch (order) { case PRE_ORDER: if(preQue.IsEmpty()) return false; item = preQue.GetFront(); preQue.DeQueue(); break; case IN_ORDER: if(inQue.IsEmpty()) return false; item = inQue.GetFront(); inQue.DeQueue(); break; case POST_ORDER: if(postQue.IsEmpty()) return false; item = postQue.GetFront(); postQue.DeQueue(); break; } return true; }

//BinarySearchTree.h #ifndef BINARYSEARCHTREE_H_INCLUDED #define BINARYSEARCHTREE_H_INCLUDED #include "Queue.h"

enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};

template struct TreeNode { ItemType info; TreeNode* left; TreeNode* right; };

template class TreeType { public: TreeType(); // done ~TreeType(); void MakeEmpty();

bool IsEmpty(); // d bool IsFull(); // d int LengthIs(); //d

bool InsertItem(ItemType item); // d bool DeleteItem(ItemType item); // d bool RetrieveItem(ItemType& item); //d

void ResetTree(OrderType order); // bool GetNextItem(ItemType& item, OrderType order);

private: TreeNode* root; Queue preQue; Queue inQue; Queue postQue; }; #include "BinarySearchTree.tpp" #endif // BINARYSEARCHTREE_H_INCLUDED

Gdrive Link : https://drive.google.com/file/d/1TG_hfHkap6FO7El5ZVOVQR-iohF0gGDJ/view?usp=sharing

Modify the TreeType class (Binary Search Tree) such that no duplicate value can be inserted. In the driver file: a. Create an integer TreeType object. b. Insert some items c. Print the tree in InOrder. Modify the TreeType class (Binary Search Tree) such that no duplicate value can be inserted. In the driver file: a. Create an integer TreeType object. b. Insert some items c. Print the tree in InOrder