How to Delete an Element from Binary Search Tree (BST) with C++ Code

What is Tree?

In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.

What is Binary Tree

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

In a tree an arbitrary node can have any number of child. But in binary tree each node can have at most two child.

What is Binary Search Tree

In computer science, a binary search tree, also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.

Delete from Binary Search Tree

To delete an element from binary search tree we need to follow 2 steps:

1. Search the element and replace with the last element. Decrease the size of BST n to n-1.
2. Recursively test and swap the new value as long as the tree don’t satisfy BST property.

C++ Code to Delete from Binary Search Tree

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,i,j;      //n is Number of Elements in the Tree and i,j are Normal Integer
    cout<<"How Much Elements in your Binary Search Tree: ";
    cin>>n;
    long Tree[n+5]; //Tree is an Array for Elements of Tree
    long Del;       //Del is the item to be deleted
    cout<<"Enter Your Binary Search Tree in Inorder:"<<endl;
    for(i=0;i<n;i++){
        cin>>Tree[i];
    }
    cout<<"What Will You Delete: ";
    cin>>Del;       //The Element What Will Be Deleted
    cout<<endl;
    for(i=0;i<n;i++){   //For Loop to Search and Replace the element
        if(Tree[i]==Del)Tree[i]=Tree[n-1];
    }
    n=n-1;              //Decrease the size of tree
    for(i=0;i<n;i++){   //For Loop to Short the Tree
        for(j=i;j<n;j++){
            if(Tree[i]>Tree[j])swap(Tree[i],Tree[j]);
        }
    }
    cout<<"Inorder Traversing After Deletion:"<<endl;
    for(i=0;i<n;i++){
        cout<<Tree[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Hope your experience with this tutorial is quite good. Comment how do you feel about this tutorial. If you have any confusion you can also comment here. Subscribe for latest posts.