How to fix my code so that when I run my code after leaf nodes is deleted the size is 8 instead of 11?

Here is my Bstree.cpp: using namespace std; #include "Bstree.h" /* Nested Node class definitions */ template  template  Bstree::Node::Node(T item) { data = item; left = nullptr; right = nullptr; } /* Outer Bstree class definitions */ template  Bstree::Bstree() { root = nullptr; order = 0; } template  Bstree::~Bstree() { recDestroy(root); } template  bool Bstree::empty() const { return root == nullptr; } template void Bstree::insert(T item) { Node* tmp; Node* newnode = new Node(item); /* If it is the first node in the tree */ if (!root) { root = newnode; order++; return; } /*find where it should go */ tmp = root; while (true) { if (tmp->data == item) { /* Key already exists. */ tmp->data = item; delete newnode; /* dont need it */ return; } else if (tmp->data > item) { if (!(tmp->left)) {/* If the key is less than tmp */ tmp->left = newnode; order++; return; } else {/* continue searching for insertion pt. */ tmp = tmp->left; } } else { if (!(tmp->right)) {/* If the key is greater than tmp */ tmp->right = newnode; order++; return; } else {/* continue searching for insertion point*/ tmp = tmp->right; } } } } template bool Bstree::inTree(T item) const { Node* tmp; if (!root) return false; /*find where it is */ tmp = root; while (true) { if (tmp->data == item) return true; else if (tmp->data > item) { if (!(tmp->left)) return false; else {/* continue searching */ tmp = tmp->left; } } else { if (!(tmp->right)) return false; else /* continue searching for insertion pt. */ tmp = tmp->right; } } } template bool Bstree::remove(const T& item) { Node* nodeptr = search(item); if (nodeptr) { remove(nodeptr); order--; return true; } return false; } template const T& Bstree::retrieve(const T& key) const { Node* nodeptr; if (!root) throw BstreeException("Exception:tree empty on retrieve()."); nodeptr = search(key); if (!nodeptr) throw BstreeException("Exception: non-existent key on retrieve()."); return nodeptr->data; } template void Bstree::inorderTraverse(FuncType apply) const { inorderTraverse(root,apply); } template long Bstree::size() const { return order; } template void Bstree::recDestroy(Node* root) { if (root) { if (root->left) recDestroy(root->left); if (root->right) recDestroy(root->right); delete root; } } template Bstree::Node* Bstree::findParent(Node* node) { Node* tmp = root; if (tmp == node) return nullptr; while(true) { //assert(tmp->data != node->data); if (!tmp) return nullptr; if (tmp->data > node->data) { //assert(tmp->left); if (tmp->left == node) return tmp; else tmp = tmp->left; } else { //assert(tmp->right); if (tmp->right == node) return tmp; else tmp = tmp->right; } } } template void Bstree::inorderTraverse(Node* node, FuncType apply) const { if (node) { inorderTraverse(node->left,apply); apply(node->data); inorderTraverse(node->right,apply); } } template Bstree::Node* Bstree::search(const T& item) const { Node* tmp = root; while(tmp) { if (tmp->data == item) return tmp; else if (tmp->data > item) tmp = tmp->left; else tmp = tmp->right; } return tmp; } template bool Bstree::remove(Node* node) { T data; Node *replacement; Node* parent = findParent(node); if (!parent) return false; if (node->left && node->right) { replacement = node->right; while (replacement->left) replacement = replacement->left; data = replacement->data; remove(replacement); node->data = data; } else { if (!(node->left) && !(node->right)) replacement = nullptr; else if (node->left == nullptr) replacement = node->right; else replacement = node->left; if (!parent) root = replacement; else if (parent->left == node) parent->left = replacement; else parent->right = replacement; delete node; } return true; } /****** IMPLEMENT AUGMENTED PRIVATE Bstree FUNCTIONS BELOW ******/ template  void Bstree::preorderTraverse(Node* node, FuncType apply) const { if (node != nullptr) { apply(node->data); preorderTraverse(node->left, apply); preorderTraverse(node->right, apply); } } template  void Bstree::postorderTraverse(Node* node, FuncType apply) const { if (node != nullptr) { postorderTraverse(node->left, apply); postorderTraverse(node->right, apply); apply(node->data); } } template  long Bstree::height(const Node* node) const { if (node == nullptr) { return -1; } else { long leftHeight = height(node->left); long rightHeight = height(node->right); return 1 + ((leftHeight > rightHeight) ? leftHeight : rightHeight); } } template  long Bstree::countLeaves(const Node* node) const { if (node == nullptr) { return 0; } else if (node->left == nullptr && node->right == nullptr) { return 1; } else { return countLeaves(node->left) + countLeaves(node->right); } } template  long Bstree::countHalves(const Node* node) const { if (node == nullptr || (node->left == nullptr && node->right == nullptr)) { return 0; } else if (node->left == nullptr || node->right == nullptr) { return 1 + countHalves(node->left) + countHalves(node->right); } else { return countHalves(node->left) + countHalves(node->right); } } template  void Bstree::trim(Node* node) { if (node != nullptr) { if (node->left != nullptr) { if (node->left->left == nullptr && node->left->right == nullptr) { delete node->left; node->left = nullptr; } else { trim(node->left); } } if (node->right != nullptr) { if (node->right->left == nullptr && node->right->right == nullptr) { delete node->right; node->right = nullptr; } else { trim(node->right); } } } } template  long Bstree::balHeight(const Node* node) const { if (node == nullptr) { return -1; } else { long leftHeight = balHeight(node->left); if (leftHeight == -2) { return -2; } long rightHeight = balHeight(node->right); if (rightHeight == -2) { return -2; } if (abs(leftHeight - rightHeight) > 1) { return -2; } return 1 + ((leftHeight > rightHeight) ? leftHeight : rightHeight); } } /****** IMPLEMENT AUGMENTED PUBLIC Bstree FUNCTIONS BELOW ******/ template void Bstree::preorderTraverse(FuncType apply) const { preorderTraverse(root, apply); } template void Bstree::postorderTraverse(FuncType apply) const { postorderTraverse(root, apply); } template long Bstree::height() const { return height(root); } template const T& Bstree::min() const { if (root == nullptr) throw BstreeException("tree is empty"); Node* current = root; while (current->left != nullptr) { current = current->left; } return current->data; } template const T& Bstree::max() const { if (root == nullptr) throw BstreeException("tree is empty"); Node* current = root; while (current->right != nullptr) { current = current->right; } return current->data; } template long Bstree::countLeaves() const { return countLeaves(root); } template long Bstree::countHalves() const { return countHalves(root); } template void Bstree::trim() { trim(root); } template  bool Bstree::isBalanced() const { return balHeight(root) != -2; }

 Here is my BstreeParser.cpp file. #include  #include  #include  #include  #include  #include "Bstree.cpp" using namespace std; /** * Displays a string and advances the cursor to the next line * @param word the string to be displayed */ void printWord(const string& word) { cout<"< words; while (inFile>>cmd) { if (cmd == "trim") { words.trim(); cout<<"leaf nodes deleted"<>token; words.remove(token); cout<<"deleted "<>token; words.insert(token); cout<<"inserted "<(pow(2,treeHeight+1))-1; cout<

Here is my Bstree.h file.

 #include  #include  #include  #include  #include  #ifndef BSTREE_H #define BSTREE_H using namespace std; /** * for report exceptions for the BSTree class */ class BstreeException { private: /** * a description of why the exception occurred */ string message; public: /** * creates an instance of this class * @param msg the reason for the exception */ BstreeException(const string& msg) { message = msg; } /** * Gives the reason for the exception * @return the reason for the exception */ string what() const { return message; } }; /** * A parametric extensible binary search tree class * @param  the binary search tree data type */ template  class Bstree { private: /** * forward declaration of a function pointer of type (const T&) -> void */ typedef void (*FuncType)(const T& item); /** * Constructs an empty binary search tree; */ /** * forward declaration of the Node class */ template  class Node; /** * the number of nodes in this tree */ long order; /** * A pointer to the root node of this tree */ Node* root; /** * An auxiliary recursive function for the destructor. * @param subtreRoot a pointer to the root of a subtree of this tree */ void recDestroy(Node* subtreeRoot); /** * Give a pointer to the parent node of the specified Node * @param node the node whose parent node is to be found * @return the pointer to the parent node of the specified Node */ Node* findParent(Node* node); /** * Traverses this tree in inorder * @param node a node of this tree * @param apply a pointer to a function of type (const T&) -> void * that is applied to the data field in the specified node */ void inorderTraverse (Node* node, FuncType apply) const; /** * Removes the specified node from the tree * @param node a pointer to the node to be removed * @return true if the node is removed; otherwise false */ bool remove(Node* node); /** * searches for the specified item in this tree * @param item the search key * @return a pointer to the node containing the item if it is found; * otherwise, nullptr */ Node* search(const T& item) const; /****** BEGIN: AUGMENTED PRIVATE FUNCTIONS ******/ /** * Traverses this tree in preorder * @param node a node of this tree * @param apply a pointer to a function of type (const T&) -> void * that is applied to the data field in the specified node */ void preorderTraverse (Node* node, FuncType apply) const; /** * Traverses this tree in postorder * @param node a node of this tree * @param apply a pointer to a function of type (const T&) -> void * that is applied to the data field in the specified node */ void postorderTraverse (Node* node, FuncType apply) const; /** * Recursively computes the height of the subtree rooted at the specified Node * @param node the root of a subtree * @return the height of the subtree rooted at the specified Node */ long height(const Node* node) const; /** * Recursively counts the number of leaf nodes in the subtree rooted at the * specified Node * @param node the root of a subtree * @return the number of leaf nodes in subtree rooted at the specified Node */ long countLeaves(const Node* node) const; /** * Recursively counts the number of half nodes in the subtree rooted at the * specified Node * @param node the root of a subtree * @return the number of half nodes in subtree rooted at the specified Node */ long countHalves(const Node* node) const; /** * Recursively removes the leaf nodes in the subtree rooted at the specified node * @param node the root of a subtree */ void trim(Node* node); /** * Gives the height if the subtree rooted at the specified node is balanced; * otherwise, -2 * @param node the root of a subtree * @return -2 if the subtree rooted at the specified node is * not balanced; otherwise the height of the subtree root at the specified node */ long balHeight(const Node* node) const; /****** END: AUGMENTED PRIVATE FUNCTIONS ******/ public: /** * Constructs an empty binary search tree; */ Bstree(); /** * Returns the binary search tree memory to the system */ virtual ~Bstree(); /** * Determines whether the binary search tree is empty. * @return true if the tree is empty; otherwise, false */ bool empty() const; /** * Inserts an item into the tree. * @param item the value to be inserted. */ void insert(T item); /** * Determines whether an item is in the tree. * @param item item with a specified search key. * @return true on success; false on failure. */ bool inTree(T item) const; /** * Deletes an item from the tree. * @param item item with a specified search key. * @return true on success; false on failure. */ bool remove(const T& item); /** * Returns the item in the tree with the specified * key. If the item does not exists, an exception occurs. * @param key the key to the item to be retrieved. * @return it with the specified key. * @throws BstreeException if the item with the specified key is not * in the tree */ const T& retrieve(const T& key) const; /** * Traverses a binary tree in inorder and applies the function visit * once for each node. * @param apply a pointer to a function of type (const T&) -> void */ void inorderTraverse(FuncType apply) const; /** * Gives the number of node in this tree * @return the size of the tree; the number of nodes in this tree. */ long size() const; /****** BEGIN: AUGMENTED PUBLIC FUNCTIONS ******/ /** * Traverses a binary tree in preorder and applies the function visit * once for each node. * @param apply a pointer to a function of type (const T&) -> void */ void preorderTraverse(FuncType apply) const; /** * Traverses a binary tree in postorder and applies the function visit * once for each node. * @param apply a pointer to a function of type (const T&) -> void */ void postorderTraverse(FuncType apply) const; /** * Gives the height of this tree * @return the height of this tree */ long height() const; /** * Gives the item in the left-most node of this tree. * @return the item in the left-most node of this tree * @throw BstreeException when this tree is empty */ const T& min() const; /** * Gives the item in the right-most node of this tree. * @return the item in the right-most node of this tree * @throw BstreeException when this tree is empty */ const T& max() const; /** * Counts the number of leaf nodes in this tree * @return the number of leaf nodes in this tree */ long countLeaves() const; /** * Counts the number of half nodes in this tree * @return the number of half nodes this tree */ long countHalves() const; /** * Removes the leaf nodes in this tree */ void trim(); /** * Determines whether this tree is balanced * @return true if this tree is balanced; otherwise, false */ bool isBalanced() const; /****** END: AUGMENTED PUBLIC FUNCTIONS ******/ }; /** * nested Node class definition * @param  the data type of the item in this node * @param  the data type of the binary search tree */ template  template  class Bstree::Node { private: /** * the data item in this Node */ T data; /** * a pointer to the left child of this Node */ Node* left; /** * a pointer to the right child of this Node */ Node* right; /** * Granting friendship - access to private members of this class to the * Bstee class */ friend class Bstree; public: /** * Constructs a node with a given data value. * @param item the data to store in this node */ Node(T item); }; #endif //BSTREE_H 

Here is my months.bst file

stats insert JANUARY stats insert FEBRUARY stats insert MARCH insert APRIL insert MAY insert JUNE insert JULY insert AUGUST insert SEPTEMBER insert OCTOBER insert NOVEMBER insert DECEMBER stats delete APRIL stats traverse trim stats traverse