## maverick786 -2

I would like to know what would be the best way to count the nodes accessed while searching for an item in a binary search tree. I have to keep a tally for each item I search for. I have included my search method from my program.

``````void BinarySearchTree::find(int d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}
tree_node* curr;
tree_node* parent;
curr = root;
while(curr != NULL)
{
if(curr->data == d)
{
found = true;
cout << " Item " << d << " found" << endl;

break;
}
else
{
parent = curr;
if(d>curr->data) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
return;
}
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
parent->left = curr->right;
else
parent->right = curr->right;
}
else // left child present, no right child
{
if(parent->left == curr)
parent->left = curr->left;
else
parent->right = curr->left;

}
return;
}
//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr)
parent->left = NULL;
else parent->right = NULL;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if((curr->right)->left != NULL)
{
tree_node* lcurr;
tree_node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->data = lcurr->data;
lcurrp->left = NULL;
}
else
{
tree_node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
}
}
return;
}``````

Thank you. I hope my question was

commented: Stop inventing code tags and learn how to do it properly, you've been here long enough to realise that by now. -2

## Ancient Dragon 5,243

A more important question is: why is that find method returning void? A find method normally locates an instance of something and returns the result to the calling function. If it didn't there would be no point to the function as it appears to be with your function.