Deletion In Binary Search Tree In C++

March 7, 2023

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:

The node to be deleted has no children.
The node to be deleted has 2 children.
The node to be deleted has 1 child.
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

Binary Search Trees in Data Structure(Introduction)

Introduction to Binary Search Tree

BST: Search in a Binary Search Tree

BST: Insertion in a Binary Search Tree

Code Implementation for Deletion in a Binary Search Tree in C++

Run

#include<bits/stdc++.h>
#include
using namespace std;
class Tree
{
public:
  int data;
  Tree *left = NULL, *right = NULL;
  // Constructor initialised
    Tree (int x)
  {
    data = x;
    left = NULL;
    right = NULL;
  }
};

Tree *Delete (Tree * root, int x)
{

  if (root == NULL)
    {
      cout << "Node not found ";
      return NULL;
    }

  if (root->data > x)
    {
      root->left = Delete (root->left, x);
    }

  else if (root->data < x)
    {
      root->right = Delete (root->right, x);
    }
  else
    {

      if (root->left == NULL)
	{
	  Tree *temp = root->right;
	  free (root);
	  return temp;
	}

      else if (root->right == NULL)
	{
	  Tree *temp = root->left;
	  free (root);
	  return temp;
	}
      else
	{

	  Tree *temp = root->right;

	  while (temp->left != NULL)
	    temp = temp->left;

	  root->data = temp->data;

	  root->right = Delete (root->right, temp->data);
	}
    }
  return root;

}

void inorder_traversal (Tree * root)
{
  if (root == NULL)
    return;
  inorder_traversal (root->left);

  cout << root->data << " ";

  inorder_traversal (root->right);

}

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);
  
  cout << "Inorder Traversal of the Binary Search Tree:";
  inorder_traversal (root);
  cout << endl;
  
  cout << "Value to be deleted : 18 \n";
  Delete (root, 18);
  cout << "Inorder Traversal :";
  inorder_traversal (root);
  cout << endl;
}

Output:

Inorder Traversal of the Binary Search Tree:8 13 14 15 16 18 19 
Value to be deleted : 18 
Inorder Traversal :8 13 14 15 16 19

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Introduction to Trees

Binary Trees

Binary Tree in Data Structures (Introduction)
Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
Inorder Postorder PreOrder Traversals Examples
- Inorder Tree Traversal in Binary Tree: C | C++ | Java
- Preorder Tree Traversal in Binary Tree : C | C++ | Java
- Postorder Tree Traversal in Binary Tree : C | C++ | Java
Tree Traversal without Recursion
- Postorder Preorder Inorder Traversal without recursion
- Inorder Tree Traversal without Recursion – C | C++ | Java
- Preorder Tree Traversal without Recursion – C | C++ | Java
- Postorder Tree Traversal without Recursion – C | C++ | Java

Binary Search Trees

Binary search tree in Data Structures (Introduction)
- BST: Introduction to Binary Search Tree
- BST: Binary Search Tree Program : C | C++ | Java
- BST: Search a node in Binary Search Tree : C | C++ | Java
- BST: Insertion in a Binary Search Tree : C | C++ | Java
- BST: Deletion in a Binary Search Tree : C | C++ | Java

Traversals

Traversal in Trees
Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
Tree Traversals: Depth First Search (DFS) : C | C++ | Java
Construct a Binary Tree from Postorder and Inorder

B – Trees

B-Tree
- B-Tree: Introduction
- B-Tree: Insertion : C | C++ | Java
- B-Tree: Deletion : C | C++ | Java

AVL Trees

AVL Trees
- AVL Trees: Introduction
- AVL Tree Insertion : C | C++ | Java
- AVL Tree Deletion : C | C++ | Java
- Insertion in a Binary Tree (Level Order) – C | C++ | Java
- Searching in Binary Tree – C | C++ | Java
- Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

Depth First Traversals – C | C++ | Java
Level Order Traversal – C | C++ | Java
Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
Find size of the Binary tree – C | C++ | Java
Find the height of binary tree – C | C++ | Java
Find maximum in binary tree – C | C++ | Java
Check whether two tree are identical- C| C++| Java
Spiral Order traversal of Tree- C | C++| Java
Level Order Traversal Line by Line – C | C++| Java
Hand shaking lemma and some Impotant Tree Properties.
Check If binary tree if Foldable or not.- C| C++| Java
check whether tree is Symmetric – C| C++| Java.
Check for Children-Sum in Binary Tree- C|C++| Java
Sum of all nodes in Binary Tree- C | C++ | Java
Lowest Common Ancestor in Binary Tree- C | C++ | Java