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.

Binary search tree in Objected-Oriented Programming, Delete a node that has two  children.  

 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


  else{ //one or zero child

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



  return *T;



This website intents to provide free and high quality tutorials, examples, exercises and solutions, questions and answers of programming and scripting languages:
C, C++, C#, Java, VB.NET, Python, VBA,PHP & Mysql, SQL, JSP, ASP.NET,HTML, CSS, JQuery, JavaScript and other applications such as MS Excel, MS Access, and MS Word. However, we don't guarantee all things of the web are accurate. If you find any error, please report it then we will take actions to correct it as soon as possible.