C++ program to delete an element into binary tree
Description:
Program :
This Program is to find the number entered by the user in the binary tree, if the element is present then delete the element from that position, and if the element is not found it will display the list of elements as it is.
For Example:
Input for tree is: 4,5,7,8,9
The entered element to delete from binary tree is : 5
Output will be :
Element deleted
After deleting array is : 4,7,8,9
//C++ program to delete an element into binary tree
using namespace std;
// tree node
struct Node
{
int data;
struct Node *left, *right;
};
// returns a new tree Node
struct Node* newNode(int data)
{
struct Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
};
//function to display all the element present in the binary tree
void display(struct Node* root)
{
if (root != NULL)
{
display(root->left);
cout<<root->data<<" ";
display(root->right);
}
}
void deletnode(struct Node *root,struct Node *node)
{
queue<struct Node*> q;
q.push(root);
// Do level order traversal until last node
struct Node* temp;
while(!q.empty())
{
temp = q.front();
q.pop();
if (temp->right)
{
if (temp->right == node)
{
temp->right = NULL;
delete(node);
return;
}
else
q.push(temp->right);
}
if (temp->left)
{
if (temp->left == node)
{
temp->left=NULL;
delete(node);
return;
}
else
q.push(temp->left);
}
}
}
// function to delete element in binary tree
void deletion(struct Node* root, int data)
{
queue<struct Node*> q;
q.push(root);
struct Node *temp;
struct Node *data_node = NULL;
// Do level order traversal to find deepest
while (!q.empty())
{
temp = q.front();
q.pop();
if (temp->data == data)
data_node = temp;
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
int x = temp->data;
deletnode(root, temp);
data_node->data = x;
}
int main()
{
int n;
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(5);
root->right->right = newNode(6);
root->left->left = newNode(4);
root->left->left->left = newNode(7);
root->left->left->right = newNode(8);
root->right->left->left = newNode(9);
root->right->right->left = newNode(10);
root->left->left->left->left = newNode(11);
root->left->left->right->left = newNode(12);
root->left->left->right->right = newNode(13);
cout<<"\nEnter the Element to be deleted: ";
cin>>n;
deletion(root,n);
cout<<"\nElement Deleted"<<endl;
cout<<"\nAfter Deletion: "<<endl;
cout<<"Elements are: ";
display(root);
cout<<endl;
return 0;
}
Comments