Use the text Binary Search Tree class as a starter, and add an iterator so my test code can iterate linearly through a tree (without recursion). Specifically, I require that you remove all uses of the Class or any other STL auxiliary storage. The iterator actually iterates through the actual tree. Limit the #include lines to only and Submit one file, named BST.h A possible starter code from the text is BST.h

#include “BST.h”
using namespace std;
// CS212, Spring 2014, Program #5
void main()
{
// Create a binary search tree for strings
BST tree;

// Add elements to the tree
tree.insert(“America”);
tree.insert(“Canada”);
tree.insert(“Russia”);
tree.insert(“France”);

// Create an Iterator
Iterator iterator = tree.begin();

tree.insert(“Texas”); // modify the tree

// Traverse a binary tree using iterators
while (iterator != tree.end())
{
cout
iterator++;
}
// Texas is missing, FIX IT!!!!
system(“pause”);
}

PreviousNext

BST.h is as follows

// Code from Liang, C++ Data Structures// changed slightly by W.P. Iverson//    Bellevue College, WA//    Spring 2015
#ifndef BST_H#define BST_H
#include #include #include #include using namespace std;
templateclass TreeNode{public:  T element; // Element contained in the node  TreeNode* left; // Pointer to the left child  TreeNode* right; // Pointer to the right child
  TreeNode(T element) // Constructor  {    this->element = element;    left = NULL;    right = NULL;  }};
template class Iterator : public std::iterator

{public:  Iterator(TreeNode* p)  {    if (p == NULL)      current = -1; // The end    else    {      // Get all the elements in inorder      treeToVector(p);      current = 0;    }  }

  Iterator operator++()  {    current++;    if (current == v.size())      current = -1; // The end    return *this;  }

  T &operator*()  {    return v[current];  }

  bool operator == (const Iterator &iterator) const  {    return current == iterator.current;

  }
  bool operator != (const Iterator &iterator) const  {    return current != iterator.current;  }
private:  int current;  vector v;  void treeToVector(TreeNode* p)  {    if (p != NULL)    {      treeToVector(p -> left);      v.push_back(p -> element);      treeToVector(p -> right);    }  }};
template class BST{public:  BST();  BST(T elements[], int arraySize);  BST(BST &tree);  ~BST();  bool search(T element) const;  virtual bool insert(T element);  virtual bool remove(T element);  void inorder() const;  void preorder() const;  void postorder() const;  int getSize() const;  void clear();  vector* >* path(T element) const;
  Iterator begin() const  {    return Iterator(root);  };
  Iterator end() const  {    return Iterator(NULL);  };
protected:  TreeNode* root;  int size;  virtual TreeNode* createNewNode(T element);
private:  void inorder(TreeNode* root) const;  void postorder(TreeNode* root) const;  void preorder(TreeNode* root) const;  void copy(TreeNode* root);  void clear(TreeNode* root);};

template BST::BST(){  root = NULL;  size = 0;}
template BST::BST(T elements[], int arraySize){  root = NULL;  size = 0;
  for (int i = 0; i
/* Copy constructor */template BST::BST(BST &tree){  root = NULL;  size = 0;  copy(tree.root); // Recursively copy nodes to this tree}
/* Copies the element from the specified tree to this tree */template void BST::copy(TreeNode* root){  if (root != NULL)  {    insert(root->element);    copy(root->left);    copy(root->right);  }}
/* Destructor */template BST::~BST(){  clear();}
/* Return true if the element is in the tree */template bool BST::search(T element) const{  TreeNode* current = root; // Start from the root
  while (current != NULL)    if (element < current->element)    {      current = current->left; // Go left    }    else if (element > current->element)    {      current = current->right; // Go right

    }    else // Element matches current.element      return true; // Element is found
  return false; // Element is not in the tree}
template TreeNode* BST::createNewNode(T element){  return new TreeNode(element);}
/* Insert element into the binary tree * Return true if the element is inserted successfully * Return false if the element is already in the list */template bool BST::insert(T element){  if (root == NULL)    root = createNewNode(element); // Create a new root  else  {    // Locate the parent node    TreeNode* parent = NULL;    TreeNode* current = root;    while (current != NULL)      if (element < current->element)      {        parent = current;        current = current->left;      }      else if (element > current->element)      {        parent = current;        current = current->right;      }      else        return false; // Duplicate node not inserted
    // Create the new node and attach it to the parent node    if (element < parent->element)      parent->left = createNewNode(element);    else      parent->right = createNewNode(element);  }
  size++;  return true; // Element inserted}
/* Inorder traversal */template void BST::inorder() const{  inorder(root);}
/* Inorder traversal from a subtree */template void BST::inorder(TreeNode* root) const

{  if (root == NULL) return;  inorder(root->left);  cout << root->element << ” “;  inorder(root->right);}
/* Postorder traversal */template void BST::postorder() const{  postorder(root);}
/** Inorder traversal from a subtree */template void BST::postorder(TreeNode* root) const{  if (root == NULL) return;  postorder(root->left);  postorder(root->right);  cout << root->element
/* Preorder traversal */template void BST::preorder() const{  preorder(root);}
/* Preorder traversal from a subtree */template void BST::preorder(TreeNode* root) const{  if (root == NULL) return;  cout << root->element << ” “;  preorder(root->left);  preorder(root->right);}
/* Get the number of nodes in the tree */template int BST::getSize() const{  return size;}
/* Remove all nodes from the tree */template void BST::clear(){  // Left as exercise}
/* Return a path from the root leading to the specified element */template vector*>* BST::path(T element) const{  vector* >* v = new vector* >();  TreeNode* current = root;

  while (current != NULL)  {    v->push_back(current);    if (element < current->element)      current = current->left;    else if (element > current->element)      current = current->right;    else      break;  }
  return v;}
/* Delete an element from the binary tree. * Return true if the element is deleted successfully * Return false if the element is not in the tree */template bool BST::remove(T element){  // Locate the node to be deleted and also locate its parent node  TreeNode* parent = NULL;  TreeNode* current = root;  while (current != NULL)  {    if (element < current->element)    {      parent = current;      current = current->left;    }    else if (element > current->element)    {      parent = current;      current = current->right;    }    else      break; // Element is in the tree pointed by current  }
  if (current == NULL)    return false; // Element is not in the tree
  // Case 1: current has no left children  if (current->left == NULL)  {    // Connect the parent with the right child of the current node    if (parent == NULL)    {      root = current->right;    }    else    {      if (element < parent->element)        parent->left = current->right;      else        parent->right = current->right;    }
    delete current; // Delete current  }  else  {

    // Case 2: The current node has a left child    // Locate the rightmost node in the left subtree of    // the current node and also its parent    TreeNode* parentOfRightMost = current;    TreeNode* rightMost = current->left;
    while (rightMost->right != NULL)    {      parentOfRightMost = rightMost;      rightMost = rightMost->right; // Keep going to the right    }
    // Replace the element in current by the element in rightMost    current->element = rightMost->element;
    // Eliminate rightmost node    if (parentOfRightMost->right == rightMost)      parentOfRightMost->right = rightMost->left;    else      // Special case: parentOfRightMost->right == current      parentOfRightMost->left = rightMost->left;
    delete rightMost; // Delete rightMost  }
  size–;  return true; // Element inserted}
#endif

really confused please help!