woolgatherer

Deletion in BST

Sep 10th, 2021 (edited)
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define fastio  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  3. #define debug(x) cout << #x << "--> " << x << endl;
  4. using namespace std;
  5. struct BSTNode
  6. {
  7.     int data;
  8.     BSTNode *left, *right;
  9. };
  10. BSTNode* CreateNode(int data)
  11. {
  12.     BSTNode *new_node = new BSTNode;
  13.     new_node->data = data;
  14.     new_node->left = NULL;
  15.     new_node->right = NULL;
  16.     return new_node;
  17. }
  18. BSTNode* Insert(BSTNode *root, int data)
  19. {
  20.     if (root == NULL)
  21.     {
  22.         root = CreateNode(data);
  23.         return root;
  24.     }
  25.     if (root->data >= data) root->left = Insert(root->left, data);
  26.     else root->right = Insert(root->right, data);
  27.     return root;
  28. }
  29. BSTNode *Construction(int n)
  30. {
  31.     BSTNode root = NULL;
  32.     while (n--)
  33.     {
  34.         int data; cin >> data;
  35.         if (data == -1) break;
  36.         root = Insert(root, data);
  37.     }
  38. }
  39. BSTNode* FindMin(BSTNode *root)
  40. {
  41.     if (root->left == NULL) return root;
  42.     FindMin(root->left);
  43. }
  44. BSTNode* Delete(BSTNode *root, int data)
  45. {
  46.     if (root == NULL) return root;
  47.     if (data < root->data) root->left = Delete(root->left, data);
  48.     else if (data > root->data) root->right = Delete(root->right, data);
  49.     else
  50.     {
  51.         if (root->left == NULL && root->right == NULL)
  52.         {
  53.             delete root;
  54.             return NULL;
  55.         }
  56.         else if (root->left == NULL)
  57.         {
  58.             BSTNode *temp = root;
  59.             root = root->right;
  60.             delete temp;
  61.         }
  62.         else if (root->right == NULL)
  63.         {
  64.             BSTNode *temp = root;
  65.             root = root->left;
  66.             delete temp;
  67.         }
  68.         else
  69.         {
  70.             BSTNode *temp = FindMin(root->right);
  71.             root->data = temp->data;
  72.             root->right = Delete(root->right, temp->data);
  73.         }
  74.     }
  75.     return root;
  76. }
  77. void InOrder(BSTNode *root)
  78. {
  79.     if (root == NULL) return;
  80.     InOrder(root->left);
  81.     cout << root->data << ' ';
  82.     InOrder(root->right);
  83. }
  84. main()
  85. {
  86.     fastio;
  87. #ifndef ONLINE_JUDGE
  88.     freopen("input.txt", "r", stdin);
  89.     freopen("output.txt", "w", stdout);
  90. #endif
  91.     int n; cin >> n;
  92.     BSTNode *root = Construction(n);
  93.     cout << "Before Deletion" << endl;
  94.     InOrder(root); cout << endl;
  95.     int data; cin >> data;
  96.     root = Delete(root, data);
  97.     cout << "After Deletion" << endl;
  98.     InOrder(root);
  99. }
  100.  
Add Comment
Please, Sign In to add comment