fork download
  1. //
  2. // main.cpp
  3. // Binary Search Tree [2]
  4. //
  5. // Created by Himanshu on 16/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. using namespace std;
  10.  
  11. struct node {
  12. int info = 0;
  13. struct node *left, *right, *parent;
  14. };
  15. typedef struct node Node;
  16.  
  17. Node* createNode (int data, Node *par) {
  18. Node* newNode = new node();
  19. newNode->info = data;
  20. newNode->left = NULL;
  21. newNode->right = NULL;
  22. newNode->parent = par;
  23.  
  24. return (newNode);
  25. }
  26.  
  27.  
  28. Node* insert (Node *root, int n, Node *par) {
  29.  
  30. if (root == NULL) {
  31. root = createNode(n, par);
  32. } else {
  33. if (root->info > n) {
  34. par = root;
  35. root->left = insert (root->left, n, par);
  36. } else {
  37. par = root;
  38. root->right = insert (root->right, n, par);
  39. }
  40. }
  41.  
  42. return root;
  43. }
  44.  
  45.  
  46. Node* search (Node *root, int n) {
  47.  
  48. if (root == NULL || root->info == n) {
  49. return root;
  50. } else {
  51. if (root->info > n) {
  52. return search (root->left, n);
  53. } else {
  54. return search (root->right, n);
  55. }
  56.  
  57. }
  58. }
  59.  
  60.  
  61. Node* findMinimum (Node *root) {
  62.  
  63. while (root->left != NULL) {
  64. root = root->left;
  65. }
  66.  
  67. return root;
  68. }
  69.  
  70.  
  71. Node* findMaximum (Node *root) {
  72.  
  73. while (root->right != NULL) {
  74. root = root->right;
  75. }
  76.  
  77. return root;
  78. }
  79.  
  80.  
  81. Node* findSuccessor (Node *root) {
  82.  
  83. if (root->right != NULL) {
  84. return findMinimum(root->right);
  85. }
  86.  
  87. Node* y = root->parent;
  88.  
  89. while (y != NULL && root == y->right) {
  90. root = y;
  91. y = y->parent;
  92. }
  93.  
  94. return y;
  95. }
  96.  
  97.  
  98. Node* deleteNode (Node *root, Node *x) {
  99. Node *par = x->parent;
  100.  
  101. if (x->left != NULL && x->right != NULL) {
  102. Node* z = findSuccessor(x);
  103. x->info = z->info;
  104. x = z;
  105. }
  106.  
  107. par = x->parent;
  108.  
  109. if (x->left != NULL) {
  110.  
  111. if (par) {
  112. if (par->left == x) {
  113. par->left = x->left;
  114. } else {
  115. par->right = x->left;
  116. }
  117. } else {
  118. root = par->left;
  119. }
  120.  
  121. // To prevent memory leak
  122. delete (x);
  123. } else if (x->right != NULL) {
  124.  
  125. if (par) {
  126. if (par->left == x) {
  127. par->left = x->right;
  128. } else {
  129. par->right = x->right;
  130. }
  131. } else {
  132. root = par->right;
  133. }
  134.  
  135. // To prevent memory leak
  136. delete (x);
  137. } else {
  138.  
  139. if (par) {
  140. if (par->left == x) {
  141. par->left = NULL;
  142. } else {
  143. par->right = NULL;
  144. }
  145. } else {
  146. root = NULL;
  147. }
  148.  
  149. // To prevent memory leak
  150. delete (x);
  151. }
  152.  
  153. return root;
  154. }
  155.  
  156.  
  157. int main() {
  158. Node *root = createNode(5, NULL);
  159. root = insert(root, 3, NULL);
  160. root = insert(root, 2, NULL);
  161. root = insert(root, 4, NULL);
  162. root = insert(root, 7, NULL);
  163.  
  164. //Searching 4 in the tree
  165. if (search (root, 4)) {
  166. cout<<"4 is present in the BST"<<endl;
  167. } else {
  168. cout<<"4 is not in the BST"<<endl;
  169. }
  170.  
  171. //Searching parent of node 3 in the tree
  172. Node *node = search (root, 3);
  173. if (node->parent) {
  174. cout<<"Parent of node 3 is "<<(node->parent->info)<<endl;
  175. } else {
  176. cout<<"Parent of node 3 is NULL"<<endl;
  177. }
  178.  
  179. //Searching successor of node 2 in the tree
  180. node = search (root, 2);
  181. if (node) {
  182. cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
  183. } else {
  184. cout<<"Successor of node 2 is NULL"<<endl;
  185. }
  186.  
  187. //Deleting node 3 in the tree
  188. cout<<"Deleting node 3"<<endl;
  189. root = deleteNode(root, search (root, 3));
  190.  
  191. // Checking if node 3 exists in the tree
  192. if (search (root, 3)) {
  193. cout<<"3 is present in the BST"<<endl;
  194. } else {
  195. cout<<"3 is not in the BST"<<endl;
  196. }
  197.  
  198. //Searching successor of node 2 in the tree
  199. node = search (root, 2);
  200. if (node) {
  201. cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
  202. } else {
  203. cout<<"Successor of node 2 is NULL"<<endl;
  204. }
  205.  
  206. //Searching successor of node 4 in the tree
  207. node = search (root, 4);
  208. if (node) {
  209. cout<<"Successor of node 4 is "<<(findSuccessor(node)->info)<<endl;
  210. } else {
  211. cout<<"Successor of node 4 is NULL"<<endl;
  212. }
  213.  
  214. return 0;
  215. }
Success #stdin #stdout 0.01s 5512KB
stdin
Standard input is empty
stdout
4 is present in the BST
Parent of node 3 is 5
Successor of node 2 is 3
Deleting node 3
3 is not in the BST
Successor of node 2 is 4
Successor of node 4 is 5