search in a binary tree

Question

I have written the following function to search for a value in a binary tree storing integer values (the function is part of a larger program):

bool tree::search(int num)       //the function belongs to class 'tree'
{
   node *temp=head;      //'head' is pointer to root node

   while(temp!=NULL)
   {
      if(temp->data==num)
         break;

      if(num>temp->data)
         temp=temp->right;

      if(num<temp->data)
         temp=temp->left;
   }

   if(temp==NULL)
      return false;
   else if(temp->data==num)
         return true;   
}    

The problem is: when I search for a value present in the tree, it runs fine. But if I search for a value not present in the tree, the program just hangs, and I have to close it. One more thing - I know we can implement the search function recursively by passing node *temp as an argument, instead of declaring it inside, and I have done so which caused the program to run correctly, but I want to know what is the problem in the above code.

I am giving the full program here, just in case it makes fault- finding easier( please note that I have written only two functions yet):

#include<iostream>
using namespace std;

struct node
{
int data;
node *left;
node *right;
};

class tree
{
public:
    node *head;    //pointer to root
    int count;     //stores number of elements in tree
    tree();
    void addnode(int);
    void deletenode(int);
    bool search(int);
    int minimum();
    int maximum();
    void inorder();
    void preorder();
    void postorder();
    void printtree();
    int mthlargest();     //finds 'm'th largest element
    int mthsmallest();    //finds 'm'th smallest element
    void convert();       //converts binary tree to linked list
};

tree::tree()
{
   head=NULL;
   count =0;
}

void tree::addnode(int num)
{
   node *temp= new node;
   temp->data=num;
   temp->left=NULL;
   temp->right=NULL;

   node **ptr=&head;          //double pointer

   while(*ptr!=NULL)
   {
      if(num>(*ptr)->data)
         ptr=&((*ptr)->right);

      if(num<(*ptr)->data)
         ptr=&((*ptr)->left);
   }

   *ptr=temp;
}


bool tree::search(int num)
{
   node *temp=head;

   while(temp!=NULL)
   {
      if(temp->data==num)
         break;

      if(num>temp->data)
         temp=temp->right;

      if(num<temp->data)
         temp=temp->left;
   }

   if(temp==NULL)
      return false;
   else if(temp->data==num)
      return true;   
}    




int main()
{
   tree ob;
   ob.addnode(2);

   ob.search(2);

   ob.search(3);

   ob.search(-1);
   ob.search(2);
   cout<<endl<<endl;

   system("pause");
   return 0;
}               

Side note : I am using Dev C++ compiler and Windows 7 OS.

Solution 1

Put an else and your problem will disappear.

Because after temp = temp->right; you must check temp again but in your original code you immediately test temp->data which may not be a valid pointer.

bool tree::search(int num)
{
    node *temp = head;

    while (temp != NULL)
    {
        if (temp->data == num)
            break;

        if (num > temp->data)
            temp = temp->right;
        else                  //  <--- Put this 'else' here
        if (num < temp->data)
            temp = temp->left;
    }

    if (temp == NULL)
        return false;

    if (temp->data == num)
        return true;

    return false;
}

Solution 2

std::set

Use a std::set; it is basically STL's binary tree. If you want to search for something, you would use count, find or lower_bound.

Implementing basic data structures are good exercises, but in production, try to use STL first, as they are implemented by professionals with specific knowledge of the compiler/platform in question. Boost is another great set of data structures and common idioms.

Comments

[Parth]

Thanks Raymond. It worked like magic. It is amazing how fast I got a reply. Thanks a lot.

[Parth]

@Alex: Yes, that has actually worked. Just curious,why do you doubt?

[Alex Chamberlain]

@Parth, I doubt because you basically have 3 cases (==, >, <) and only one can be true, so not sure why else helped, other than to improve readability (which you need to work on in general - Google "Artistic Style C++ formatting")

[Admin]

@Alex, the else worked because in a case where the second if condition works, it'll increment the temp to temp->right... now the third if condition is now checked with the new value of temp. Here, your temp will probably be incremented to temp->right without checking for the NULL value. I guess that's why you are getting a problem when the number is not there in the tree.