Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
- #define debug(x) cout << #x << "--> " << x << endl;
- using namespace std;
- struct BSTNode
- {
- int data;
- BSTNode *left, *right;
- };
- BSTNode* CreateNode(int data)
- {
- BSTNode *new_node = new BSTNode;
- new_node->data = data;
- new_node->left = NULL;
- new_node->right = NULL;
- return new_node;
- }
- BSTNode* Insert(BSTNode *root, int data)
- {
- if (root == NULL)
- {
- root = CreateNode(data);
- return root;
- }
- if (root->data >= data) root->left = Insert(root->left, data);
- else root->right = Insert(root->right, data);
- return root;
- }
- BSTNode *Construction(int n)
- {
- BSTNode root = NULL;
- while (n--)
- {
- int data; cin >> data;
- if (data == -1) break;
- root = Insert(root, data);
- }
- }
- BSTNode* FindMin(BSTNode *root)
- {
- if (root->left == NULL) return root;
- FindMin(root->left);
- }
- BSTNode* Delete(BSTNode *root, int data)
- {
- if (root == NULL) return root;
- if (data < root->data) root->left = Delete(root->left, data);
- else if (data > root->data) root->right = Delete(root->right, data);
- else
- {
- if (root->left == NULL && root->right == NULL)
- {
- delete root;
- return NULL;
- }
- else if (root->left == NULL)
- {
- BSTNode *temp = root;
- root = root->right;
- delete temp;
- }
- else if (root->right == NULL)
- {
- BSTNode *temp = root;
- root = root->left;
- delete temp;
- }
- else
- {
- BSTNode *temp = FindMin(root->right);
- root->data = temp->data;
- root->right = Delete(root->right, temp->data);
- }
- }
- return root;
- }
- void InOrder(BSTNode *root)
- {
- if (root == NULL) return;
- InOrder(root->left);
- cout << root->data << ' ';
- InOrder(root->right);
- }
- main()
- {
- fastio;
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int n; cin >> n;
- BSTNode *root = Construction(n);
- cout << "Before Deletion" << endl;
- InOrder(root); cout << endl;
- int data; cin >> data;
- root = Delete(root, data);
- cout << "After Deletion" << endl;
- InOrder(root);
- }
Add Comment
Please, Sign In to add comment