C++ program to delete an element into binary search tree

C++ program to delete an element into binary search tree

This Program is to find the number entered by the user and search it in the binary search tree, if the element is present it will send it's position and delete the element from that position, and if the element is not found it will display element not fond message and will print 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 search tree is : 5

Output will be :
5 found at position 2
Element deleted
After deleting array is : 4,7,8,9

Program :

//C++ program to delete an element into binary search tree #include <bits/stdc++.h> using namespace std; // tree node struct Node { int data; Node *left, *right; }; // returns a new tree Node Node* newNode(int data) { Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp; } // A function to create binary search tree. Node* Tree(Node* root, int data) { // Create node using data entered by user. Node *temp = newNode(data); Node *temp1 = new Node; temp1 = root; // If root is null then the node created. if(root == NULL) root = temp; else { // Search the position for the new node to be inserted. while(temp1 != NULL) { if(temp1->data < data ) { if(temp1->right == NULL) { // If current node is NULL then the value will be inserted here and break. temp1->right = temp; break; } // Shift pointer to the left. temp1 = temp1->right; } else if(temp1->data > data) { if(temp1->left == NULL) { temp1->left = temp; break; } // Shift pointer to the left. temp1 = temp1->left; } } } return root; } //function to display all the element present in the binary search tree void display(struct Node* root) { if (root != NULL) { display(root->left); cout<<root->data<<" "; display(root->right); } } // A function to search item in a binary search tree. void Search(Node *root, int data) { int pos = 0; Node *temp = new Node; temp = root; // Run the loop until temp points to a NULL pointer. while(temp != NULL) { pos++; if(temp->data == data) { cout<<"\nData found at position: "<<pos; return; } // Shift pointer to left child. else if(temp->data > data) temp = temp->left; // Shift pointer to right child. else temp = temp->right; } cout<<"\n Data not found"; return; } //function to find the minimum Node* Min(Node*root) { while(root->left!=NULL) { root=root->left; } return root; } //function to delete the element entered by the user Node* Delete( Node* root,int value) { if(root==NULL) return root; else if(value< root->data) { root->left= Delete(root->left,value); } else if(value> root->data) { root->right= Delete(root->right,value); } // Node deletion else { // Leaf Node if(root->left==NULL&&root->right==NULL) { delete root; root=NULL; return root; } //one child else if(root->left==NULL) { struct Node* temp=root; root=root->right; delete temp; return root; } else if(root->right==NULL) { struct Node* temp=root; root=root->left; delete temp; return root; } //child else { struct Node*temp=Min(root->right); root->data=temp->data; root->right=Delete(root->right,temp->data); } } return root; } int main() { char ch; int n, arr[20],size; Node *root = new Node; root = NULL; cout<<"Enter the size of array : "; cin>>size; cout<<"Enter the elements in array : "; for(int i=0;i<size;i++) { cin>>arr[i]; } // Construct the binary search tree. for(int i = 0; i < size; i++) root = Tree(root, arr[i]); cout<<"\nEnter the Element to be deleted: "; cin>>n; Search(root, n);           Delete(root,n); cout<<"\nElement Deleted"<<endl; cout<<"\nAfter Deletion: "<<endl; cout<<"Elements are: "; display(root); cout<<endl; return 0; }

More Articles of Mandeep Sheoran:

Name Views Likes
C++ program to insert an element into binary tree 6240 19
C++ program to find an element into binary tree 772 16
C++ std::is_void 573 15
C++ program to find the closest element in binary search tree 916 19
C++ program to replace every element with the least greater element on its right 574 12
C++ program to delete an element into binary tree 785 24
C++ program to find maximum element between two nodes of binary search tree 700 20
C++ std::remove_copy_if with std::vectors 548 11
C++ program to print duplicate elements from the binary search tree 2937 15
C++ program to find depth of the deepest odd level node in binary tree 575 23
C++ program to remove duplicate elements from the binary search tree 1555 20
C++ std::rotate_copy with std::vector 530 14
C++ std::copy_n with std::vector 638 22
C++ std::copy_if with std::vector 1552 18
C++ program to print all the elements of binary search tree 7107 22
C++ std::reverse_copy with std::list 599 18
C++ program to print all the elements of binary tree 1158 18
C++ program to print all full nodes in a binary tree 573 25
C++ program to find sink odd nodes in binary tree 580 15
C++ std::is_copy_assignable 596 22
C++ program to check whether a binary tree is a full binary tree or not using recursion 609 19
C++ std::is_copy_constructible 618 27
C++ program to delete an element into binary search tree 2874 18
C++ std::reverse_copy with std::vector 488 18
C++ std::rotate with std::vector 641 15
C++ program to check for symmetric binary tree using recursion 599 25
C++ program to maximum sum from a tree with adjacent levels not allowed 552 15
C++ std::copy_n with std::list 595 21
C++ program to check if two trees are identical using recursion 546 15
C++ std::copy_n 874 21
C++ std::copy_if with std::list 999 19
C++ program to print the nodes at odd levels of a tree 562 13
C++ program to find lowest common ancestor in a binary tree 690 29
C++ program to find depth of the deepest odd level leaf node 494 13
C++ std::remove_copy_if with std::list 667 20
C++ program to add all greater values to every node in a given binary search tree 638 15