-1

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

Votes + Comments
Stop inventing code tags and learn how to do it properly, you've been here long enough to realise that by now.
2
Contributors
1
Reply
2
Views
9 Years
Discussion Span
Last Post by Ancient Dragon
0

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 topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.