delete_nodes_BST.cpp

#include<bits/stdc++.h>
usingnamespacestd;

classTree
{
public:

int val;
 Tree *left;
 Tree *right;

public:

//class constructor called when any object or pointer is created without any parameter.
Tree() 
 {
 val=0;
 left=nullptr;
 right=nullptr;
 }

//class constructor called when an object or pointer is called while passing an argument (val). 
Tree(int val) 
 {
this->val=val;
this->left=nullptr;
this->right=nullptr;
 }

//builds a Binary Tree taking (int) value as an argument and returns the root to the tree built. 
 Tree* buildTree(int val)
 {
if(this==nullptr)
 {
 Tree *temp = newTree(val);
return temp;
 }
else
 {
 Tree *temp=nullptr;
if(this->val>val)
 {
 temp=this->left->buildTree(val);
this->left=temp;
 }
else
 {
 temp=this->right->buildTree(val);
this->right=temp;
 }
returnthis;
 }
 }

//RECURSIVE DFS PREORDER
voidpreOrder() 
 {
if(this!=nullptr)
 {
 cout<<this->val<<",";
this->left->preOrder();
this->right->preOrder();
 }
 }
};

Tree* deleteNode(Tree *root, int val)
{
if(root==nullptr)
returnnullptr;
else
 {
if(root->val>val)
 root->left=deleteNode(root->left,val);
elseif(root->val<val)
 root->right=deleteNode(root->right,val);
else
 {
if(root->left!=nullptr)
 {
 Tree *temp=root->left;
 Tree *trav=temp->right;
if(trav==nullptr)
 {
 temp->right=root->right;
 root=temp;
 }
else
 {
while(trav->right!=nullptr)
 {
 temp=trav;
 trav=trav->right;
 }
 temp->right=trav->left;
 root->val=trav->val;
 trav->left=NULL;
 }
 }
elseif(root->right!=nullptr)
 {
 Tree *temp=root->right;
 Tree *trav=temp->left;
if(trav==nullptr)
 {
 temp->left=root->left;
 root=temp;
 }
else
 {
while(trav->left!=nullptr)
 {
 temp=trav;
 trav=trav->left;
 }
 temp->left=trav->right;
 root->val=trav->val;
 trav->right=NULL;
 }
 }
else
 root=nullptr;
 }
return root;
 }
}

intmain()
{
 vector<int>test={8,5,3,6,11,10,9,12};
 Tree *root=nullptr;
for(int i:test)
 root=root->buildTree(i);
 cout<<"The tree: ";
 root->preOrder();
 root=deleteNode(root,6);
 cout<<"\nThe tree after deletion: ";
 root->preOrder();
}