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