fork download
copy 
  1. /*
  2. Binary Search Tree (BST - iterative )
  3.  
  4. struct Node {
  5.    int data;
  6.    struct Node *left;
  7.    struct Node *right;
  8. }
  9.  
  10. Node *mostlyLeft(Node *root) {
  11.  
  12.      while(root->left) root = root->left;
  13.  
  14.  
  15.      return root;
  16. }
  17.  
  18. Node *remove( Node *root, int key ) {
  19.  
  20.       if(root == NULL) {
  21.         return root;
  22.       } else if(root->data > key) {
  23.              root->left = remove(root->left, key);
  24.      } else if(root->data < key) {
  25.              root->right = remove(root->right, key)
  26.      } else {
  27.  
  28.             if(root->left == NULL && root->right == NULL) {
  29.                    free(root);
  30.                     return NULL
  31.             }   else if(root->left == NULL) {
  32.                   Node *temp = root->right;
  33.                   free(root);
  34.                   return temp;
  35.            }  else if(root->right == NULL) {
  36.                   Node *temp = root->left;
  37.                   free(root);
  38.                   return temp;
  39.  
  40.            }  else if(root->left !=NULL && root->right != NULL) {
  41.                 Node *temp = mostlyLeft(root->right)
  42.                      root->data = temp->data;
  43.                      root->right = remove(root->right, temp->data)
  44.            }
  45.      }
  46. }
  47.  
  48. */
  49.  
  50.  
  51. #include <iostream>
  52.  
  53. struct Node {
  54.  
  55.      int data;
  56.      struct Node *left;
  57.      struct Node *right;
  58. };
  59.  
  60. struct Node *root = NULL;
  61.  
  62. void insert(int val) {
  63.  
  64.      struct Node *curr, *new_node;
  65.  
  66.      if(root == NULL) {
  67.  
  68.           root = (struct Node*)malloc(sizeof(struct Node));
  69.  
  70.           root->data = val;
  71.           root->left = NULL;
  72.           root->right = NULL;
  73.  
  74.      } else {
  75.  
  76.             curr = root;
  77.  
  78.             while(1) {
  79.  
  80.                   if(val < curr->data) {
  81.  
  82.                       if(curr->left) {
  83.  
  84.                           curr = curr->left;
  85.  
  86.                       } else {
  87.  
  88.                           new_node = (struct Node*) malloc(sizeof(struct Node));
  89.  
  90.                           new_node->data = val;
  91.                           new_node->left= NULL;
  92.                           new_node->right = NULL;
  93.                           curr->left = new_node;
  94.                           break;
  95.  
  96.                       }
  97.  
  98.  
  99.                   } else {
  100.  
  101.  
  102.                          if(curr->right) {
  103.  
  104.                               curr = curr->right;
  105.  
  106.                          }  else {
  107.  
  108.                               new_node = (struct Node*)malloc(sizeof(struct Node));
  109.                               new_node->data = val;
  110.                               new_node->left = NULL;
  111.                               new_node->right = NULL;
  112.                               curr->right = new_node;
  113.  
  114.                               break;
  115.  
  116.                          }
  117.  
  118.                   }
  119.  
  120.             }
  121.  
  122.  
  123.      }
  124. }
  125.  
  126. void inorder(struct Node *node) {
  127.  
  128.      if(node->left) inorder(node->left);
  129.  
  130.      printf("%d ", node->data);
  131.  
  132.      if(node->right) inorder(node->right);
  133. }
  134.  
  135. void postorder(struct Node*node) {
  136.  
  137.      if(node->left) postorder(node->left);
  138.  
  139.      if(node->right) postorder(node->right);
  140.  
  141.      printf("%d ", node->data);
  142. }
  143.  
  144. void preorder(struct Node *node) {
  145.  
  146.      printf("%d ", node->data);
  147.  
  148.      if(node->left) preorder(node->left);
  149.  
  150.      if(node->right) preorder(node->right);
  151. }
  152.  
  153.  
  154. int search(int val) {
  155.  
  156.      //get the pointer of the BST
  157.     struct Node *curr = root;
  158.  
  159.     int found = 0;
  160.  
  161.     while(!found && curr) {
  162.  
  163.          if(curr->data == val) {
  164.  
  165.                       found = 1;
  166.          } else {
  167.  
  168.                      if(val < curr->data) {
  169.  
  170.                          curr = curr->left;
  171.                      } else {
  172.                          curr = curr->right;
  173.                      }
  174.          }
  175.  
  176.  
  177.     }
  178.  
  179.     return found;
  180. }
  181.  
  182. void remove(int val) {
  183.  
  184.  
  185.      struct Node *curr = root, *parent, *next;
  186.  
  187.      int found = 0;
  188.  
  189.      while(!found && curr) {
  190.  
  191.             if(curr->data == val) {
  192.  
  193.                found = 1;
  194.  
  195.             }  else {
  196.  
  197.                if(val < curr->data) {
  198.                   parent = curr;
  199.                   curr = curr->left;
  200.                }  else {
  201.                   parent = curr;
  202.                   curr = curr->right;
  203.                }
  204.             }
  205.      }
  206.  
  207.     if( found )  {
  208.  
  209.  
  210.           if(curr->left == NULL && curr->right == NULL) {
  211.  
  212.                  if(parent->data < curr->data) parent->right = NULL;
  213.                             else
  214.                                                parent->left = NULL;
  215.                  free(curr);
  216.  
  217.           } else if(curr->left == NULL && curr->right != NULL) {
  218.  
  219.                  next = curr->right;
  220.  
  221.                  if(parent->data < curr->data) parent->right = next;
  222.                               else
  223.                                                parent->left = next;
  224.                  free(curr);
  225.  
  226.           } else if(curr->left != NULL && curr->right == NULL) {
  227.  
  228.                  next = curr->left;
  229.  
  230.                  if(parent->data < curr->data) parent->right = next;
  231.                                     else
  232.                                                parent->left = next;
  233.                   free(curr);
  234.  
  235.           } else if(curr->left != NULL && curr->right != NULL) {
  236.  
  237.                  struct Node *p, *c;
  238.  
  239.                  c = curr->left;
  240.  
  241.                 while(c->right) {
  242.  
  243.                     p = c;
  244.  
  245.                     c = c->right;
  246.                 }
  247.  
  248.                 curr->data = c->data;
  249.  
  250.                 next = c->left;
  251.  
  252.                 if(p->data < c->data) p->right = next;
  253.                              else
  254.                                       p->left = next;
  255.  
  256.                 free(c);
  257.  
  258.           }
  259.  
  260.  
  261.           printf("The node is removed!");
  262.  
  263.     } else {
  264.  
  265.  
  266.          printf("The Node not found!");
  267.     }
  268.  
  269.  
  270.  
  271. }
  272.  
  273. int main(int argc, char const *argv[]) {
  274.  
  275.   insert(8);
  276.   insert(3);
  277.   insert(10);
  278.   insert(1);
  279.   insert(7);
  280.   insert(12);
  281.   insert(21);
  282.   printf("\nInorder: \n");
  283.   inorder(root);
  284.   printf("\nPreorder: \n");
  285.   preorder(root);
  286.   printf("\npostorder: \n");
  287.   postorder(root);
  288.  
  289.   int search_key = 1;
  290.  
  291.   int ans = search(search_key);
  292.  
  293.   if(ans == 1) printf("The key is found in BST\n");
  294.           else
  295.                printf("The key is not found in BST\n");
  296.  
  297.   int remove_key = 7;
  298.  
  299.   remove(remove_key);
  300.  
  301.   inorder(root);
  302.  
  303.   return 0;
  304. }
Success #stdin #stdout 0.01s 5308KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Inorder: 
1 3 7 8 10 12 21 
Preorder: 
8 3 1 7 10 12 21 
postorder: 
1 7 3 21 12 10 8 The key is found in BST
The node is removed!1 3 8 10 12 21
https://ideone.com/fEXrQx
BST iteratively
language:
C++14 (gcc 8.3)
created:
321 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!