Binary Search Tree Functions

I have these two functions that i have to do and then insert them into the code given. i have attempted to do the code so could come check for me whether its correct.

implement a function, countLeaves, that takes a parameter, a pointer to the root node of a binary search tree, and returns the number of leaves in a binary tree.

implement a function, nodeCount, that returns the number of nodes in the BST tree.

my codings done for functions

Code:

---

int CountLeaves(Node<Item>* tree)
 {
  if(tree == NULL)
    return 0;
  if (tree->left == NULL && tree->right == NULL)
    return 1;
  else
    return (CountLeaves(tree->left) + CountLeaves(tree->right));
 }

---

Code:

---

int NodeCount(TreeNode<ItemType>* root)
{
  if(root == NULL) //base case - if the return 0 if node doesn't exist (don't count it)
      return 0;
  else
      return 1 + NodeCount(root->left) + NodeCount(root->right); //return 1 for the current node, and add the amount of nodes in the left and right subtree
}

---

the code given which we have to put the functions

Code:

---

#include "BST.h"

using namespace std;

// BST public member functions
BST::BST()
{
    root = NULL;
}

BST::~BST()
{
  destroy(root);
}

void BST::insertIntoBST(const string s)
{
    root = insert(s, root);
}

void BST::deleteFromBST(const string s)
{
    // not in 3SFE504 course notes
    // implemented on 17 October 2004 by Ping Brennan
    if (!isEmptyBST())
    {
      deleteNode(s);
    }
    else
    {
      cout << "Cannot delete from the empty tree " << endl;
    }
}

void BST::printBST() const
{
    if (!isEmptyBST())
    {
        print(root);
    }
    else
    {
        cout << "Tree empty" << endl;
    }
}

bool BST::isInBST(const string s) const
{
    return search(s, root);
}

bool BST::isEmptyBST() const
{
    return root==NULL;
}

// Private member functions
// recursive

/* inserts s into the tree pointed to by ptr */
Node* BST::insert(string s, Node* ptr)
{
    /* if the pointer is pointing to nothing then we are at the end of
      out branch, so allocate new space for a node, insert data, and
      set its left and right offspring pointers to NULL otherwise
      traverse the tree to find a place to insert the new data */
    if (ptr == NULL)
    {
      ptr = new Node(s);
    }
    else
    {
      if (s < ptr->word)
      {
          ptr->left = insert(s, ptr->left);
      }
      else
      {
          ptr->right = insert(s, ptr->right);
      }
    }
    return ptr;
}

void BST::deleteNode(string s)
{
    /* finds the node containing the
        string, s, (if any) to be deleted.
        If the node containing s is found in the BST, this function
        calls the function deleteFromTree to delete the node
    */   
    Node* current;            // pointer to traverse the tree
    Node* trailCurrent;        // pointer behind current
    bool found = false;

    current = root;
    trailCurrent = root;
 
    /* searches for the node containing s (if any) */
    while (current != NULL && !found)
    {
        if (current->word == s)
        {
            found = true;
        }
        else
        {
            trailCurrent = current;
            if (current->word > s)
            {
              current = current->left;
            }
            else
            {
              current = current->right;
            }
          }
      } // end while

      if (current == NULL)
      {
        cout << "The delete item is not in the list."<< endl;
      }
      else if (found)
          {
              if (current == root)
              {
                deleteFromTree(root);
              }
              else if (trailCurrent->word > s)
                  {
                      deleteFromTree(trailCurrent->left);
                  }
                  else
                  {
                      deleteFromTree(trailCurrent->right);
                  }
            }
} //end deleteNode


                                             
void BST::deleteFromTree(Node* &p)
{
    Node* current;                  // pointer to traverse the tree
    Node* trailCurrent;            // pointer behind current
    Node* temp;                    // pointer to delete the node

    if (p == NULL)
        cerr << "Error: The node to be deleted is NULL."
            << endl;
    else if (p->left == NULL && p->right == NULL)
          {
            /* Case 1: the node to be deleted has no left and
                right subtrees, i.e. the node to be deleted is a leaf
            */
            temp = p;
            p = NULL;
            delete temp;
          }
          else if (p->left == NULL)
              {
                  /* Case 2: the node to be deleted has no left subtree,
                    i.e. the  left subtree is empty, but it has a
                    nonempty right subtree */
                  temp = p;
                  p = temp->right;
                  delete temp;
              }
              else if (p->right == NULL)
                    {
                      /* Case 3: the node to be deleted has no right
                          subtree, i.e. the right subtree is empty, but
                          it has a nonempty left subtree */
                      temp = p;
                      p = temp->left;
                      delete temp;
                    }
                    else
                    {
                      /* Case 4: the node to be deleted has nonempty 
                          left and right subtrees. */
                      current = p->left;
                      trailCurrent = NULL;
                     
                      while (current->right != NULL)
                      {
                          trailCurrent = current;
                          current = current->right;
                      } // end while
   
                      p->word = current->word;
                      if (trailCurrent == NULL) // current did not move;
                                          // current == p->left; adjust p
                      {
                          p->left = current->left;
                      }
                      else
                      {
                          trailCurrent->right = current->left;
                      }
                      delete current;
                    } // end else
} //end deleteFromTree
   

/* deallocates the nodes in the tree pointed to by ptr
  post order traversal used */
void BST::destroy(Node* ptr)
{
    if (ptr != NULL)
    {
        destroy(ptr->left);
        destroy(ptr->right);

        // destructor test code:
        //
        delete ptr;
      }
}

// displays the tree pointed to by ptr
// inorder traversal used
void BST::print(Node* ptr) const
{
    if (ptr != NULL)
    {
        print(ptr->left);
        cout << ptr->word << endl;
        print(ptr->right);
    }
}

// returns true if s is present in the tree pointed to by ptr
// otherwise returns false
bool BST::search(string s, Node* ptr) const
{
    if (ptr == NULL)
    {
        return false;
    }
    else if (s == ptr->word)
          {
              return true;

          }
          else if (s < ptr->word)
              {
                  return search(s, ptr->left);
              }
              else
              {
                  return search(s, ptr->right);
              }
}

---

could someone help me on this and check whether what i have done is correct. i can provide the header files if needed!