rectify the code of binary search tree search function in c++(updated question)

Question

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 25-Nov-14 23:13pm

Varun Galar

Updated 25-Nov-14 23:19pm

v4

Add a Solution

2 solutions

Solution 1

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.

Posted 25-Nov-14 23:56pm

Richard MacCutchan

Comments

nv3 26-Nov-14 7:49am

Good catch.

Richard MacCutchan 26-Nov-14 8:47am

Thanks; as I said, easy to catch.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Stefan_Lang · Accepted Answer · 2014-11-27T20:33:00

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.