fork download
copy 
  1. #include <stdio.h>
  2. #include <malloc.h>
  3.  
  4. typedef struct Node {
  5.        struct Node * left;
  6.        struct Node * right;
  7.        int data;
  8. } Node;
  9.  
  10. Node *insert(Node * root, int key) {
  11.  
  12.       if(root == NULL) {
  13.         root = (Node*)malloc(sizeof(Node));
  14.         root->left= NULL;
  15.         root->right = NULL;
  16.         root->data = key;
  17.       } else {
  18.         if(root->data < key) {
  19.           root->right = insert(root->right, key);
  20.         } else if(root->data > key) {
  21.           root->left = insert(root->left, key);
  22.         }
  23.       }
  24.  
  25.       return root;
  26. }
  27.  
  28. Node *mostlyLeft(Node *root) {
  29.       while(root->left) {
  30.         root = root->left;
  31.       }
  32.       return root;
  33. }
  34.  
  35. Node *delete(Node *root, int key) {
  36.  
  37.      if(root == NULL) {
  38.  
  39.        return root;
  40.  
  41.      } else if(root->data > key) {
  42.  
  43.        root->left = delete(root->left, key);
  44.  
  45.      } else if(root->data < key) {
  46.  
  47.        root->right = delete(root->right, key);
  48.  
  49.      } else {
  50.  
  51.        if(root->left == NULL && root->right == NULL) {
  52.  
  53.           free(root);
  54.           return NULL;
  55.  
  56.        } else if(root->left == NULL) {
  57.  
  58.           Node *temp = root->right;
  59.           free(root);
  60.           return temp;
  61.  
  62.        } else if(root->right == NULL) {
  63.  
  64.           Node *temp = root->left;
  65.           free(root);
  66.           return temp;
  67.  
  68.        } else if (root->left != NULL && root->right != NULL)  {
  69.  
  70.          Node *temp = mostlyLeft(root->right);
  71.                root->data = temp->data;
  72.                root->right = delete(root->right, temp->data);
  73.        }
  74.  
  75.  
  76.      }
  77.  
  78.      return root;
  79. }
  80.  
  81. int search(Node *root, int key) {
  82.     if(root == NULL) {
  83.        return 0;
  84.     } else if(root->data > key) {
  85.       return search(root->left, key);
  86.     } else if(root->data < key) {
  87.       return search(root->right, key);
  88.     } else {
  89.       return 1;
  90.     }
  91. }
  92.  
  93. void inorder(Node*node) {
  94.      if(node) {
  95.        inorder(node->left);
  96.        printf("%d ", node->data);
  97.        inorder(node->right);
  98.      }
  99. }
  100.  
  101. void preorder(Node*node) {
  102.      if(node) {
  103.        printf("%d ", node->data);
  104.        inorder(node->left);
  105.        inorder(node->right);
  106.      }
  107. }
  108.  
  109. void postorder(Node*node) {
  110.      if(node) {
  111.        inorder(node->left);
  112.        inorder(node->right);
  113.        printf("%d ", node->data);
  114.      }
  115. }
  116.  
  117. int main(int argc, char const *argv[]) {
  118.  
  119.   Node *root = NULL;
  120.  
  121.   root = insert(root, 10);
  122.   insert(root, 5);
  123.   insert(root, 4);
  124.   insert(root, 18);
  125.   insert(root, 1);
  126.   insert(root, 5);
  127.   insert(root, 19);
  128.   insert(root, 23);
  129.   insert(root, 22);
  130.   insert(root, 14);
  131.   printf("%s", "Inorder Traversal: ");
  132.   inorder(root);
  133.   printf("\n%s", "Preorder Traversal: ");
  134.   preorder(root);
  135.   printf("\n%s", "Postorder Traversal: ");
  136.   postorder(root);
  137.   int keysearch = 111, r;
  138.   r = search(root, keysearch);
  139.   if(r == 1) {
  140.     printf("\nThe key %d Found in BST.", keysearch);
  141.   } else {
  142.     printf("\nThe key %d Not Found in BST.", keysearch);
  143.   }
  144.   int keydelete = 10;
  145.   printf("\nDelete %d and inorder\n", keydelete);
  146.   delete(root, keydelete);
  147.   inorder(root);
  148.   return 0;
  149. }
  150.  
Success #stdin #stdout 0.01s 5300KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Inorder Traversal: 1 4 5 10 14 18 19 22 23 
Preorder Traversal: 10 1 4 5 14 18 19 22 23 
Postorder Traversal: 1 4 5 14 18 19 22 23 10 
The key 111 Not Found in BST.
Delete 10 and inorder
1 4 5 14 18 19 22 23
https://ideone.com/tdjjGu
BST recursive
language:
C (gcc 8.3)
created:
329 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!