Click here to Skip to main content
15,917,177 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
C++
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<process.h>

struct tree_node
{
	tree_node *left;
	tree_node *right;
	int data;
	char r;
} ;
class bst
{
	tree_node *root;
	public:
	bst()
	{
		root=NULL;
	}
	int isempty()
	{
		return(root==NULL);
	}
	void insert(int item);
	void inordertrav();
	void inorder(tree_node *);
	void postordertrav();
	void postorder(tree_node *);
	void preordertrav();
	void preorder(tree_node *);
	int search(tree_node * ,int);
};
void bst::insert(int item)
{
	tree_node *p=new tree_node;
	tree_node *previous;
	p->data=item;
	p->left=NULL;
	p->right=NULL;
	previous=NULL;
	if(isempty())
		root=p;
	else
	{
		tree_node *current;
		current=root;
		while(current!=NULL)
		{
			previous=current;
			if(item<current->data)
				current=current->left;
			else
				current=current->right;
		}
		if(item<previous->data)
			previous->left=p;
		else
			previous->right=p;
	}
}
void bst::inordertrav()
{
	inorder(root);
}
void bst::inorder(tree_node *current)
{
	if(current!=NULL)
	{
		inorder(current->left);
		cout<<"  "<<current->data<<"     ";
		inorder(current->right);
	}
}
void bst::postordertrav()
{
	postorder(root);
}
void bst::postorder(tree_node *current)
{
	if(current!=NULL)
	{
		postorder(current->left);
		postorder(current->right);
		cout<<"  "<<current->data<<"     ";
	}
}
void bst::preordertrav()
{
	preorder(root);
}
void bst::preorder(tree_node *current)
{
	if(current!=NULL)
	{
		cout<<"  "<<current->data<<"     ";
		preorder(current->left);
		preorder(current->right);
	}
}

int bst::search(tree_node* root,int data) {
	int r;
	if(root == NULL) {
	   //	r='f';
		return 0;
	}
	else if (root != NULL){
	if(root->data == data) {
	   //	r='t';
		return 1;
	}
	}
	else if(data <= root->data) {
	      return search(root->left,data);
	}
	else {
	      return search(root->right,data);
	}

}
void main()
{
	int digit;
	bst b;
	tree_node *root;
	/*b.insert(52);
	b.insert(25);
	b.insert(50);
	b.insert(15);
	b.insert(40);
	b.insert(45);
	b.insert(20); */
	cout<<"insert the nodes in the BT";
	cout<<"enter integer: to quit enter 0";
	cin>>digit;
	while (digit!=0)
	{
		b.insert(digit);
		cin>>digit;
	}
		 cout<<"inorder"<<endl;
	b.inordertrav();
	cout<<endl<<"postorder"<<endl;
	b.postordertrav();
	cout<<endl<<"preorder"<<endl;
	b.preordertrav();
	int number;
	cout<<"Enter number be searched\n";
	cin>>number;
	//If number is found, print "FOUND"
	int c;
	c=b.search(root,number);
	cout<<"returned value"<<c;
	if (c==1) cout<<"Found\n";
	else cout<<"Not Found\n";
	getch();
}


The search function is always returning the same value whether it is in the BST or not.
Please help me to figure out the error.
The above code has no compile error.
Posted
Updated 25-Nov-14 23:19pm
v4

The above code does have a compile error, but you must have it suppressed. At the end of the function there is no return statement for the code path described below.

In your search function, if root contains a data value that is equal to your input parameter, then it will return 1. However, if the value is not equal to your input parameter, it will fall through the rest of the code and return some random (but possibly the same) value. Easy to spot by stepping through the code with the debugger.
 
Share this answer
 
Comments
nv3 26-Nov-14 7:49am    
Good catch.
Richard MacCutchan 26-Nov-14 8:47am    
Thanks; as I said, easy to catch.
Change
C++
int bst::search(tree_node* root,int data) {
    int r;
    if(root == NULL) {
       //   r='f';
        return 0;
    }
    else if (root != NULL){
    if(root->data == data) {
       //   r='t';
        return 1;
    }
    }
    else if(data <= root->data) {
          return search(root->left,data);
    }
    else {
          return search(root->right,data);
    }

}

to
C#
int bst::search(tree_node* root,int data) {
    int r;
    if(root == NULL) {
       //   r='f';
        return 0;
    }
    else if (root != NULL){
    if(root->data == data) {
       //   r='t';
        return 1;
    }
    else if(data <= root->data) {
          return search(root->left,data);
    }
    else {
          return search(root->right,data);
    }
    }

}

Of course, the issue would have been easier to spot if you had indented the code correctly:

C#
int bst::search(tree_node* root,int data) {
    int r;
    if(root == NULL) {   // test root value
       //   r='f';
        return 0;
    }
    else if (root != NULL){ // test root value (hmmm... see comment below)
        if(root->data == data) {
           //   r='t';
            return 1;
        }
    }
    else if(data <= root->data) { // testing again, in case root is neither "NULL" nor "not NULL" (wait, what?)
          return search(root->left,data);
    }
    else {
          return search(root->right,data);
    }

}


It would have been even more obvious if you had removed the redundand second test:
C++
int bst::search(tree_node* root,int data) {
    int r;
    if(root == NULL) {       // checking for NULL here
       //   r='f';
        return 0;
    }
    else /*if (root != NULL)*/{ // if I'm here, then root can not be NULL!
        if(root->data == data) {
           //   r='t';
            return 1;
        }
    }
    else if(data <= root->data) { // <-- this will issue a compile error now!
          return search(root->left,data);
    }
    else {
          return search(root->right,data);
    }

}


Lessons learned:
1. format the code correctly to improve readability and the ability to spot errors before even compiling the code
2. check your conditional statements for redundant checks and have the compiler help you find logical errors
3. Once you fix the syntax error in the last version, the compiler will likely notice that there is a return missing (see solutuion 1); probably it didn't bother with an error message before because it realized it would never get to the end of the function anyway.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900