deleting node in BST

[csstudent123]

Hello. Please help me in learning deleting BST node through recursion.

In my class my tutor wrote something like this for BST delete node struc:

struct node{

   //data
   node* root, *left, *right;
}

why not

struct node{

   //data
   node* *left, *right;
} 

node * root;

whats the difference?

[coder777]

whats the difference?

The difference is that you don't need to search for the root node with the first node while you need to with the second.

In other words: the first approach needs more data for being faster

[csstudent123]

I wrote a deleteNode bst function but its giving me segmentation fault:

The algorithm is like this:

find value to be deleted;
if found and it is leaf delete it
else if found value is greater than root value in right subtree
else value in left subtree

if value in right subtree
traverse right nodes
if found right node and value to be deleted link previous value with value next of found value
else if value is less that right node while in right subtree
traverse left nodes
delete if found and link

here is my code

void bst:: deleteN(hwareItem*& root, hwareItem*& curr, char barcode[]){
	
	hwareItem* prev, *traverse, *goToLeaf, *save, *tmp;
	char path;
	curr=findNode(root, curr, barcode);
	traverse=root;
	prev=root;
	tmp=NULL;
	goToLeaf=root;
	if((curr->right) && (curr->left==NULL)){
		delete curr;
		curr=NULL;
		
		}
	
	else if(strcmp(curr->barcode, traverse->barcode)>0){
		path='R';
		
		traverse=traverse->right;
		save=traverse;
		cout<<"Right subtree exists. Value in right subtree"<<endl;
		
		
		
		while(goToLeaf!=NULL){
			//prev=goToLeaf;
			goToLeaf=goToLeaf->right;
			if(goToLeaf->right->right==NULL){
				//goToLeaf=goToLeaf->left;
				strcpy(goToLeaf->barcode,goToLeaf->left->barcode);
				cout<<"val: "<<goToLeaf->barcode<<endl;
				break;}
				
			}
		//prev=root;
		while(traverse!=NULL){
			if(strcmp(curr->barcode, traverse->barcode)==0){
				if(traverse->left==NULL){
					prev->right=curr->right;
					//strcpy(prev->right->barcode, curr->right->barcode);
					delete curr;
					curr=NULL;}
				else if(traverse->right==NULL){
					prev->left=curr->left;
					//strcpy(prev->left->barcode, curr->left->barcode);
					delete curr;
					curr=NULL;
					}
				else{
					strcpy(tmp->barcode, curr->barcode);
					strcpy(curr->barcode,goToLeaf->barcode);
					strcpy(goToLeaf->barcode, tmp->barcode);
					delete goToLeaf;
					goToLeaf=NULL;
					
					}
					
				
				}
			traverse=traverse->right;
			
			}
			traverse=save;
			prev=root;
			//goToLeaf=traverse;
			
			
			while(traverse!=NULL){
			if(strcmp(curr->barcode, traverse->barcode)==0){
				if(traverse->left==NULL){
					prev->left=curr->right;
					//strcpy(prev->left->barcode, curr->right->barcode);
					delete curr;
					curr=NULL;}
				else if(traverse->right==NULL){
					prev->left=curr->left;
					//strcpy(prev->left->barcode, curr->left->barcode);
					delete curr;
					curr=NULL;
					}
				else{
					
					strcpy(tmp->barcode, curr->barcode);
					strcpy(curr->barcode,goToLeaf->barcode);
					strcpy(goToLeaf->barcode, tmp->barcode);
					delete goToLeaf;
					goToLeaf=NULL;
					
					}	
				
				}
		
			traverse=traverse->left;
		}}
	else{ 
		path='L';
		
		cout<<"Left subtree exists. Value in left subtree"<<endl;
		traverse=traverse->left;
		}
	
		
	}

[coder777]

I'd guess that line 11 is supposed to be:

if((curr->right==NULL) && (curr->left==NULL)){ // Note: curr->right==NULL

But none the less you cannot just delete curr and set it to NULL. You need to set the pointer to this in the root leave to NULL as well.

I'd say that the algorithm is simplier:

Remove the current leave.
Traverse the right/left (if any) and add them to the tree.
An 'AddToTree(...)' (or so) exist already, doesn't it?

[csstudent123]

yess it does...solved it..thanks :)

[Archibong]

Please, someone should help me with this assignment, thank you

You need to write a code, which will calculates results, depending on the values that user enters to the running software: i.e.
1) Y=1/A i.e Y – is result, A is a variable, and it is known, that the variable A has values from the interval: A_begin, A_end, and the step (A_step) which describes the step (speed) in which variables varies. Result should be printed out in „table“ that it has columns, and we can easy recognize, which column has values of Y, and which column has values of A, etc.

Let say; we have several examples: A_begining = 1, A_end = 4, A_step = 1, that the software should make calculations on several A values (Y=1/1, Y=1/2, Y=1/3, Y=1/4) and print out the values of A and result of Y, every time it will make calculations.

If we have A_begining = 1, A_end = -4, A_step = -1, your software should make all posible calculations with A values (1, 0, -1, -2, -3, -4) , and print result on spcreen. You need to make software that it will not HANG, and run correclty on any A values, that user will enter to it. All examples that you need to pay attention when caculations can be done, and when not, what condition of A_begin vs A_end and A_step should be analyzed where explain in 116 room.
The result in table could be provided such way (or like this)



!-----------------!---------------!

! value of A ! result Y !

!-----------------!---------------!

! 1 ! 1.0 !

! 2

And so on.

The same is for others three calculations.

Y=B/SQRT(A), B and A – provided bu user

Y = C/(B-A), all values provided bu user, BUT:

Y=xN X and N provided by user