Binary Search Tree

The building block of the binary search tree is its node.

template<typename T>
struct BSTNode{
   T storage;
   BSTNode* left;
   BSTNode* right;
};

The component storage contains the relevant data. The components left and right are pointers to the children of the node. The left child has its value smaller than the value of the parent and the right child has its value larger than the value of the parent.

In order for this to work, the structure T must have a comparison operator.

One example of such class is City.

class City{
private:
 int p;
 string c;
 string n;
public:
 void setValues(int x, string y, string z){p=x;c=y;n=z;}
 int population() const{return p;}
 string country() const{return c;}
 string name() const{return n;}
 int operator<(const City & ) const;
};
int City::operator<(const City & t) const{
 if(n<t.n){return 1;}
 if(n>t.n){return 0;}
 if(c<t.c){return 1;}
 if(c>t.c){return 0;}
 if(p<t.p){return 1;}
 return 0;
}
struct BSTNode{
 City storage;
 BSTNode* left;
 BSTNode* right;
};

The new element can be inserted in the tree with the following function

BSTNode* insert(BSTNode* root, City const & z){
 if(root==nullptr){
  BSTNode* temp=new BSTNode;
  temp->left=nullptr;temp->right=nullptr;
  temp->storage=z;
  return temp;
 }
 if(z < root->storage){
  root->left=insert(root->left,z);
  return root;
 }
 if(root->storage < z){
  root->right=insert(root->right,z);
  return root;
 }
 return root;
}

If one attempts to insert an element that is already in the tree, then the tree will not change.

Deleting an element from the tree is more complicated. The simplest requests to fulfill are the one in the node that needs to be deleted does not have a left or a right child. If the node has both children, then this node will not be deleted. The value will be replaced with the smallest element of the right-subtree which then can be easily deleted because it has not children of its own.

The necessary functions are given in the code block below

BSTNode* deleteMinimum(BSTNode* root){
 if(root==nullptr) return nullptr;
 if(root->left==nullptr){
  BSTNode* updatedRoot=root->right;
  delete root;
  return updatedRoot;
 }
 root->left=deleteMinimum(root->left);
 return root;
}
BSTNode* deleteMaximum(BSTNode* root){
 if(root==nullptr) return nullptr;
 if(root->right==nullptr){
  BSTNode* updatedRoot=root->left;
  delete root;
  return updatedRoot;
 }
 root->right=deleteMaximum(root->right);
 return root;
}
City minTree(BSTNode* root){
 if(root==nullptr){
  City c;
  c.setValues(-1,"noCountry","noName");
  return c;
 }
 if(root->left==nullptr) return root->storage;
 return minTree(root->left);
}
City maxTree(BSTNode* root){
 if(root==nullptr){
  City c;
  c.setValues(-1,"noCountry","noName");
  return c;
 }
 if(root->right==nullptr) return root->storage;
 return maxTree(root->right);
}
BSTNode* delNode(BSTNode* root, City const & z){
 if(root==nullptr) return nullptr;
 if(root->storage<z){
  root->right=delNode(root->right,z);
  return root;
 }
 if(z<root->storage){
  root->left=delNode(root->left,z);
  return root;
 }
 if(root->left==nullptr){
  BSTNode* updatedRoot=root->right;
  delete root;
  return updatedRoot;
 }
 if(root->right==nullptr){
  BSTNode* updatedRoot=root->left;
  delete root;
  return updatedRoot;
 }
 City mC=minTree(root->right);
 root->right=deleteMinimum(root->right);
 root->storage=mC;
 return root;
}