Binary Search Tree Help

[tykkimies]

I am trying to make the search function for a binary search tree to determine if a value is in the tree. I then want to output back to the user whether it is in the tree or not. This all works, however when i call the search function from my remove function it displays This item is in the tree. I can see why this happens, but i don't know how i can fix it.

bool binarySearchTree::search(int input, bool key){
	key = false;

	if(root_ptr == NULL){
		cout<< "The Tree is Empty";
		return NULL;
	}

	current_ptr = root_ptr;
	 while(current_ptr !=NULL){
		 if(current_ptr ->data == input){
			 cout<< "Item is in the Tree!" << endl;
			 key = true;
			 return key;
			 break;
		 }

		 else{
			 parent_ptr = current_ptr;
			 if(input > current_ptr ->data){
				 current_ptr = current_ptr ->right;
			 }
			 else
				 current_ptr = current_ptr ->left;
		 }
	 }
		 if(!key){
			 cout<< "Data Not in tree" << endl;
			 return false;
		 }
}

Whenever i ask to remove an item that is in the tree obviously the item will be in it before it gets removed, and this is why it displays "Item is in the Tree!"?

Anyone know another place i could put this to work properly?

Also if you would like to see other parts of my code, like my header file, and main just ask. Thanks.

[endLine]

I'm not sure why you are calling the search function from the remove function. Can you post your remove function code so I can see what is going on with that?

[tykkimies]

remove function. The reason i call the search from within the remove is because i need to first see if the item is in the tree inorder to remove it. I originally had a search algorithm within my remove function, but my teacher wants a search function to be seperate so the user can always search for anything. So i figured i would try to use the search function with remove, which does work except for my little hiccup. Anyway here is the remove:

void binarySearchTree::remove(int leaf){
	bool found = false;

	search(leaf, found);

	 //Node has one child
	 if((current_ptr ->left == NULL && current_ptr ->right !=NULL) || (current_ptr ->left != NULL && current_ptr ->right == NULL)){
		 if(current_ptr ->left == NULL && current_ptr ->right !=NULL){
			 if(parent_ptr ->left == current_ptr){
				 parent_ptr ->left = current_ptr ->right;
				 delete current_ptr;
			 }
			 else{
				 parent_ptr ->right = current_ptr ->right;
				 delete current_ptr;
			 }
		 }

		 //left child, no right child
		 else{
			 if(parent_ptr ->left = current_ptr){
				 parent_ptr ->left = current_ptr ->left;
				 delete current_ptr;
			 }
			 else{
				 parent_ptr ->right = current_ptr ->left;
				 delete current_ptr;
			 }
		 }
		 return;
	 }

	 //Leaf Node
	 if(current_ptr ->left == NULL && current_ptr ->right == NULL){
		 if(parent_ptr ->left == current_ptr){
			 parent_ptr ->left = NULL;
		 }
		 else{
			 parent_ptr ->right = NULL;
		 }
		 delete current_ptr;
		 return;
	 }

	 //Two Children
	 if(current_ptr ->left !=NULL && current_ptr ->right !=NULL){
		 node* check;
		 check = current_ptr ->right;
		 if(check ->right == NULL && check ->left == NULL){
			 current_ptr = check;
			 delete check;
			 current_ptr ->right = NULL;
		 }
		 else{
			 if(current_ptr ->right ->left != NULL){
				 node* lcurr;
				 node* curr;
				 curr = current_ptr ->right;
				 lcurr = current_ptr ->right ->left;
				 while(lcurr != NULL){
					 curr = lcurr;
					 lcurr = lcurr ->left;
				 }
				 current_ptr ->data = lcurr ->data;
				 delete lcurr;
				 curr ->left = NULL;

			 }
			 else{
				 node* temp;
				 temp = current_ptr ->right;
				 current_ptr ->data = temp ->data;
				 current_ptr ->right = temp ->right;
				 delete temp;
			 }
		 }
		 return;

	 }
}

[Peter87]

You should probably remove the cout statements inside the search function. If you really want to print that information you can do that from outside the function by checking the return value.

[o1vk4iN6]

Why would you search for it and not return a pointer to the element? You are basically doing the search operation twice, which is inefficient. When you go to remove the element, you search for it, and if it isn't there than you don't touch anything and just return.