C++ Deletion of Nodes in BST














































C++ Deletion of Nodes in BST



Deletion in Binary Search Tree

Possible Cases

Since this is a binary search tree, we are guaranteed that each node will have at most two children. Given that, we can assume the following scenarios:

  • The node we want to delete has zero children
  • The node we want to delete has one child
  • The node we want to delete has two children

Come up with solutions for the different cases

1) Node to be deleted is leaf: Simply remove from the tree. 

              50                            50
/ \ delete(20) / \
30 70 ---------> 30 70
/ \ / \ \ / \
20 40 60 80 40 60 80

2) Node to be deleted has only one child: Copy the child to the node and delete the child 

              50                            50
/ \ delete(30) / \
30 70 ---------> 40 70
\ / \ / \
40 60 80 60 80

3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used. 
 

              50                              60
/ \ delete(50) / \
40 70 ---------> 40 70
/ \ \
60 80 80

The important thing to note is, inorder successor is needed only when right child is not empty. In this particular case, inorder successor can be obtained by finding the minimum value in right child of the node.

Construct a BST as given below and perform Delete Operations



CODE

/*C++ Program for deleting an element in BST */
#include<iostream>
using namespace std;
/* A binary search tree node has data, pointer to left child
and a pointer to right child */

struct Node
{

int data;
Node* left;
Node* right;
/*For Creating New Node*/
Node(
int val)
{
left =
NULL;
right =
NULL;
data = val;
}
};
/*Insertion Function*/
Node* insert(Node* rt,int val)
{
if(rt==NULL)
{
rt =
new Node(val);
}
else if(val<=rt->data)
{
rt->left = insert(rt->left,val);
}
else
{
rt->right = insert(rt->right,val);
}
return rt;
}

/*Inorder Traversal*/
void inorder(Node* rt)
{
if(rt!=NULL)
{
inorder(rt->left);
cout<<rt->data<<" ";
inorder(rt->right);
}
}
/*For Finding the minimum element in Right Subtree*/
Node* findMin(Node* rt)
{
Node* c = rt;
while(c && c->left != NULL)
c = c->left;
return c;
}
/*Deletion Function*/
Node* DeleteFun(Node* rt,int val)
{
if(rt == NULL)
return NULL;
else if(val < rt->data)
rt->left = DeleteFun(rt->left,val);
else if(val > rt->data)
rt->right = DeleteFun(rt->right,val);
else
{
if(rt->left == NULL && rt->right == NULL)
{
delete rt;
rt =
NULL;
}
else if(rt->left == NULL)
{
Node* temp = rt->right;
delete rt;
rt = temp;
}
else if(rt->right == NULL)
{
Node* temp = rt->left;
delete rt;
rt = temp;
}
else
{
Node* temp = findMin(rt->right);
rt->data = temp->data;
rt->right = DeleteFun(rt->right,rt->data);
}
return rt;
}
}
/* DRIVER FUNCTION */
int main()
{
int k;
/*In Insert function root is local thus why we are returning and storing root*/
/*Initially the Root is NULL*/
Node* root =
NULL;
root = insert(root,
50);
root = insert(root,
30);
root = insert(root,
20);
root = insert(root,
40);
root = insert(root,
70);
root = insert(root,
60);
root = insert(root,
80);
/* Inorder Traversal of BST is always in Ascending Order*/
cout<<"Inorder Traversal of Tree is "<<endl;
inorder(root);
root = DeleteFun(root,
20);
cout<<"\nAfter Deleting 20"<<endl;
inorder(root);
root = DeleteFun(root,
30);
cout<<"\nAfter Deleting 30"<<endl;
inorder(root);
root = DeleteFun(root,
50);
cout<<"\nAfter Deleting 50"<<endl;
inorder(root);
return 0;
}


OUTPUT
Inorder Traversal of Tree is
20 30 40 50 60 70 80
After Deleting 20
30 40 50 60 70 80
After Deleting 30
40 50 60 70 80
After Deleting 50
40 60 70 80

More Articles of Shaik Ismail:

Name Views Likes
C++ Shutdown Using C++ Code 385 1
C++ Majority Element (LeetCode) 328 0
C++ Missing Number(LeetCode) 155 0
C++ Count set bits in an integer 551 0
C++ Power of Two Leetcode BitManipulation 446 0
C++ Single Number LeetCode Bit Manipulation 214 0
C++ Radix Sort 186 0
C++ Wave Sort 161 0
C++ Counting Sort 155 0
C++ DNF Algorithm for Sorting 0,1,2 320 0
C++ Merge Sort 157 0
C++ Quick Sort 232 0
C++ Insertion Sort 153 0
C++ Selection Sort 167 0
C++ Bubble Sort 204 0
C++ DFS for a Graph 182 0
C++ BFS in Graph 197 0
C++ Graph Representation (Adjacency list) 160 0
C++ Graph Representation 181 0
C++ Basics of Graph Data Structure 162 0
C++ Diameter of a Binary Tree 193 0
C++ Check if a binary tree is a BST or not 493 0
C++ Heap Sort 364 0
C++ Deletion in Heaps 380 0
C++ Insertion of Elements in Heap 157 0
C++ Basics of Heap Data Structure 152 0
C++ Deletion in AVL Trees 138 0
C++ AVL Rotations 238 0
C++ AVL Tree 144 0
C++ Deletion of Nodes in BST 495 0
C++ Kth Largest Element in BST 149 0
C++ Kth Smallest Element in BST 175 0
C++ Searching in BST 137 0
C++ Insertion of Nodes in BST 138 0
C++ Basics of BST Part - 1 337 0
C++ Binary Tree is a SumTree or Not 122 0
C++ Sum of all leaf nodes 126 0
C++ Identical Binary Trees 132 0
C++ Mirror Binary Tree 190 0
CPP Project or program to get six subjects marks of a student and then calculate its total, average and percentage and display them on the screen 145 0
C++ Lowest Common Ancestor 143 0
C++ Bottom View of a Binary Tree 183 0
C++ Top View of a Binary Tree 131 0
C++ Vertical Order Traversal of a Binary Tree 198 0
C++ Level Order Traversal of a Binary Tree 172 0
C++ Height of the Binary Tree (Code) 131 0
C++ Binary Tree Representation and Traversals (Code) 169 1
C++ Binary Tree 135 0
C++ Basics of Tree Data Structure PART - 2 147 0
Tree 133 1
Basics of Tree Data Structure PART - 1 98 0

Comments