﻿ C++ exercises and solutions: Delete node from binary tree

# C++ exercises and solutions: Delete node from binary tree

### Delete node from binary search tree

Step 4: Delete a node of the binary search tree

Deleting a node from the binary search tree is a more complicate process. To delete a node there are two important things to condition:

1. The target node has two children nodes: To delete a node that has two children node, you need to replace the data value of the node with the data value of the smallest node of its right child node. Then the smallest node used in replacement will be delete.

2. The target node has only one or zero child node. We will need a temporary pointer to point to the node. If the node to be deleted has only right child node(Its left child is empty), we let the node takes its right child node's address, otherwise we let the node takes its left child node. This process also can be applied to the node that has zero child. The temporary pointer is deleted after this deletion process.

//Delete node
template <class Type>
Node<Type> *BSTree<Type>::Delete(Node<Type> **T,const Type Tar){
Node<Type> *Min,*Temp;
if((*T)==NULL) return NULL;
else if(Tar<(*T)->data) {return Delete(&(*T)->pLeft,Tar); }//look in the left
else if(Tar>(*T)->data) return Delete(&(*T)->pRight, Tar);//look in the right
else{ //found node to delete

if((*T)->pLeft && (*T)->pRight) //two children
{
Min=findmin((*T)->pRight);
(*T)->data=Min->data;
(*T)->pRight=Delete(&(*T)->pRight,(*T)->data);

}

else{ //one or zero child

Temp=*T;
if((*T)->pLeft==NULL) {(*T)=(*T)->pRight; }
else if((*T)->pRight==NULL) {(*T)=(*T)->pLeft;}

delete(Temp);

}

return *T;
}

}