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)
   {
        cout << " " << d <<" Data not found! "<<endl;
        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

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

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.

This article has been dead for over six months. Start a new discussion instead.