# How to Delete a Node in a Binary Tree

3 Scenarios for Deleting a Node in a Binary Tree:

1. Node to be deleted is a leaf node

2. Node to be deleted has only one child

3. Node to be deleted has two children

## Case 1: Deleting a Leaf Node

• In this case the node has no child

## Case 2: Deleting a Node with One Child

• In this case we have to link the node to remove child to the node to remove parent or in other words link Grandparent to Grand Child

## Case 3: Deleting a Node with Two Child

• Tricky

Logic

• Find Minimum value in Right-Subtree
• Copy the Value in the targeted Node
• Delete Duplicate from Right-Subtree

Another Approach:

• Find the Max in the Left-Subtree
• Copy the value in the targeted Node
• Delete Duplicate from Left-Subtree

Code

``````#include<iostream>
using std::cout;
using std::endl;
using std::cin;
#include <queue>
using std::queue;

struct Node {
int data;
struct Node *left;
struct Node *right;
};

// print InOrder
void Inorder(Node *root) {
if(root == NULL)
{
return;
}
Inorder(root->left);          // Visit left subtree
cout << root->data << endl;  // Print data
Inorder(root->right);        // Visit right subtree
}

// Function to Insert Node in a Binary Search Tree

Node* Insert(Node *root,int data) {
// Return pointer which is a memory address

if(root == NULL) {
root = new Node();
root->data = data;
root->left = root->right = NULL;
}

else if(data <= root->data)
{
root->left = Insert(root->left,data);
}
else
{
root->right = Insert(root->right,data);
}

return root;  // Return Root Address
}
Node* FindMin(Node* root)
{
Node* current = root;

while (current && current->left != NULL){
current = current->left;
}
return current;
}

Node* FindMax(Node* root)
{
Node* current = root;

while (current && current->right != NULL){
current = current->right;
}
return current;
}

Node* Delete(Node *root, int data){
if (root == NULL)
{
return root;
}
else if(data < root->data)
{
root->left = Delete(root->left,data);
}
else if(data > root->data){
root->right = Delete(root->right,data);
}
else{

if (root->left == NULL && root->right == NULL) {
// Case 1: No Child
delete root;
root = NULL;
}
// Case 2: One Child
else if(root->left == NULL){
Node *temp = root;
root = root->right;
delete temp;
}
else if(root->right == NULL){
Node *temp =root;
root = root->left;
delete temp;
}
else{
// Case 3: 2 childern (Finding Min Value in Right-Subtree)
// Node *temp = FindMin(root->right);
//root->data = temp->data;
//root->right  = Delete(root->right, temp->data);

// Case 3: 2 childern Alternative Way (Finding Max vale in Left-Subtree !)
Node *temp = FindMax(root->left);
root->data = temp->data;
root->left  = Delete(root->left, temp->data);
}
}
return root;
}

void printLevelOrder(Node *root)
{
// Base Case
if (root == NULL)
{
return;
}
queue<Node*> q;

q.push(root);

while (q.empty() == false)
{
int NodeCount = q.size();

while (NodeCount > 0)
{
Node *Node = q.front();
cout << Node->data << " ";
q.pop();
if (Node->left != NULL)
q.push(Node->left);
if (Node->right != NULL)
q.push(Node->right);
NodeCount--;
}
cout << endl;
}
}

int main() {

Node* root = NULL;

root = Insert(root,12);
root = Insert(root,15);
root = Insert(root,5);
root = Insert(root,3);
root = Insert(root,7);
root = Insert(root,9);
root = Insert(root,11);
root = Insert(root,8);
root = Insert(root,1);
root = Insert(root,13);
root = Insert(root,14);
root = Insert(root,17);
root = Insert(root,20);
root = Insert(root,18);

cout << "Before Deleting Any Nodes: " << endl;
printLevelOrder(root);

// Delete Leaf Node with One On
cout << "Delete Node Leaf Node (deleting 18) " << endl;

root = Delete(root, 18);
printLevelOrder(root);
cout << endl;

// Now lets delete!!!!
cout << "Deleting Node with one Child (3): " << endl;
root = Delete(root, 3);
printLevelOrder(root);
cout << endl;

cout << "Delete Node with two Childern (Deleting 15): " << endl;
//Delete Node with two childern
root = Delete(root, 15);
printLevelOrder(root);
cout << endl;

}
``````

Output:

``````Before Deleting Any Nodes:
12
5 15
3 7 13 17
1 9 14 20
8 11 18
Delete Node Leaf Node (deleting 18)
12
5 15
3 7 13 17
1 9 14 20
8 11

Deleting Node with one Child (3):
12
5 15
1 7 13 17
9 14 20
8 11

Delete Node with two Childern (Deleting 15):
12
5 14
1 7 13 17
9 20
8 11
``````