## 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!