# Deletion In Binary Search Tree In C++

## Deletion In Binary Search Tree:

A binary search tree is a tree in which the data in left subtree is less than the root and the data in right subtree is greater than the root. There are three cases in deletion .In this article, deletion is performed in C++.  ## Three Possible Cases In Deletion:

1. The node to be deleted has no children.
2. The node to be deleted has 2 children.
3. The node to be deleted has 1 child.
4. In this example, 8, 13 and 18 are going to be deleted.

Case 1: The node to be deleted has no child nodes.

If the node to be deleted from the tree has no child nodes, the node is simple deleted from the tree since it is a leaf node.

##### Step 1:
• The node to be deleted is 8.
##### Step 2:
• Since the node 8 is a leaf node consisting of no child nodes, it is simply removed from the tree.
• The BST structure after deletion is shown as follows. Case 2: The node to be deleted has a single child node

If the node to be deleted has a single child node, the target node is replaced from its child node and then the target node is simply deleted.

##### Step 3:
• The node to be deleted is 13.
##### Step 4:
• Since the target node has a single child, i.e, 14, we replace the node 13 with node 14.
• The BST structure after deletion is shown as follows. Case 3: The node to be deleted has two child nodes

If the node to be deleted has two child nodes, we first find the inorder successor of the node and replace the target node with the inorder successor.

##### Step 5:
• The next node to be deleted is 18.
##### Step 6:
•  We can see from the image given that the target node 18 has two child nodes.
• We find the inorder successor of the target node. In this case the inorder successor is 19. Inorder successor can be defined as the smallest element of the right subtree.
• After replacing the target node with the inorder successor, the node is simply deleted.
• The final BST is shown as follows ## Code:

#include <bits/stdc++.h>
using namespace std;
class Tree {
public:
int data;
Tree* left = NULL,*right = NULL;
// Constructor initialised
Tree(int x) {
data = x;
left = NULL;
right = NULL;
}
};
void inorder_traversal (Tree *root) {
if (root == NULLreturn;
// Visit Left subtree
inorder_traversal(root -> left);
// Print the data
cout << root -> data << ” “;
// Visit right subtree
inorder_traversal(root -> right);

}
Tree* Delete(Tree* rootint x) {
// If leaf is encountered
if (root == NULL) {
cout << “Node not found “;
return NULL;
}
// Recur for left subtree
if (root -> data > x) {
root -> left = Delete(root -> left, x);
}
// Recur for right subtree
else if (root -> data < x){
root -> right = Delete(root -> right , x);
}
else {
// Left child NULL
if (root -> left == NULL) {
Tree *temp = root -> right;
free(root);
return temp;
}
// Right child NULL
else if (root -> right == NULL) {
Tree *temp = root -> left;
free(root);
return temp;
}
else {
// Finding the inorder successor
Tree *temp = root -> right;
// Finding the leftmost node in right subtree
while (temp -> left != NULL) temp = temp -> left;
// Changing value of root
root -> data = temp -> data;
// Deleting the leftmost node;
root -> right = Delete(root -> righttemp -> data);
}
}
return root;

}
int main() {
Tree *root = new Tree(15);
root -> left = new Tree(13);
root -> right = new Tree(18);
root -> left -> left = new Tree(8);
root -> left -> right = new Tree(14);
root -> right -> left = new Tree(16);
root -> right -> right = new Tree(19);
int first_delete = 8, second_delete = 13, third_delete = 18;
cout << “Inorder Traversal – “;
inorder_traversal(root);
cout << endl;
cout << endl;

cout << “8 deleted \n;
Delete(root, first_delete);
cout << “Inorder Traversal – “;
inorder_traversal(root);
cout << endl;
cout << endl;

cout << “13 deleted \n;
Delete(root, second_delete);
cout << “Inorder Traversal – “;
inorder_traversal(root);
cout << endl;
cout << endl;

cout << “18 deleted \n;
Delete(root, third_delete);
cout << “Inorder Traversal – “;
inorder_traversal(root);
cout << endl;

}

## Output:

`Inorder Traversal - 8 13 14 15 16 18 19 8 deleted Inorder Traversal - 13 14 15 16 18 19 13 deleted Inorder Traversal - 14 15 16 18 19 18 deleted Inorder Traversal - 14 15 16 19 `

O(n)

O(h)