fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<stdbool.h>
  4.  
  5. struct TreeNode
  6. {
  7.     int data;
  8.     TreeNode* left;
  9.     TreeNode* right;
  10. };
  11.  
  12.  
  13. TreeNode* createNode(int data)
  14. {
  15.     TreeNode *temp = (TreeNode *)malloc(sizeof(TreeNode));
  16.     temp->data = data;
  17.     temp->left = temp->right = NULL;
  18.     return temp;
  19. }
  20. /**
  21. TreeNode* test(TreeNode* root)
  22. {
  23.     root = createNode(5);
  24.     printf("[From TEST] %d\n", (root)->data);
  25.     return root;
  26. }
  27. **/
  28.  
  29.  
  30. TreeNode* insertion(TreeNode *root, int key)
  31. {
  32.     if(root==NULL)
  33.     {
  34.         root = createNode(key);
  35.         return root;
  36.     }
  37.     else
  38.     {
  39.         if(key>root->data)
  40.         {
  41.             root->right = insertion(root->right, key);
  42.         }
  43.         else if(key<root->data)
  44.         {
  45.             root->left = insertion(root->left, key);
  46.         }
  47.         return root;
  48.     }
  49. }
  50.  
  51. bool search_BST(TreeNode* root, int key)
  52. {
  53.     if(root==NULL)
  54.     {
  55.         return false;
  56.     }
  57.     else
  58.     {
  59.         if(root->data == key) return true;
  60.         else if(key>root->data)
  61.         {
  62.             bool friend_answer = search_BST(root->right, key);
  63.             return friend_answer;
  64.         }
  65.         else
  66.         {
  67.             bool friend_answer = search_BST(root->left, key);
  68.             return friend_answer;
  69.         }
  70.     }
  71. }
  72.  
  73. void inorder(TreeNode* root)
  74. {
  75.     if(root==NULL) return;
  76.  
  77.     inorder(root->left);
  78.  
  79.     printf("%d ", root->data);
  80.  
  81.     inorder(root->right);
  82. }
  83.  
  84. int find_minimum(TreeNode* root)
  85. {
  86.     if(root==NULL)
  87.     {
  88.         return -1;
  89.     }
  90.     else if(root->left==NULL)
  91.         return root->data;
  92.     else
  93.     {
  94.         int answer = find_minimum(root->left);
  95.         return answer;
  96.     }
  97. }
  98.  
  99.  
  100. TreeNode* find_minimum_iterative(TreeNode* root)
  101. {
  102.     if(root==NULL)
  103.     {
  104.         return NULL;
  105.     }
  106.  
  107.     TreeNode* temp = root;
  108.     while(temp->left!=NULL)
  109.     {
  110.         temp = temp->left;
  111.     }
  112.     return temp;
  113. }
  114.  
  115. int find_maximum(TreeNode* root)
  116. {
  117.     if(root==NULL)
  118.     {
  119.         return -1;
  120.     }
  121.     else if(root->right==NULL)
  122.         return root->data;
  123.     else
  124.     {
  125.         int answer = find_maximum(root->right);
  126.         return answer;
  127.     }
  128. }
  129.  
  130. TreeNode* find_maximum_iterative(TreeNode* root)
  131. {
  132.     if(root==NULL)
  133.     {
  134.         return NULL;
  135.     }
  136.  
  137.     TreeNode* temp = root;
  138.     while(temp->right!=NULL)
  139.     {
  140.         temp = temp->right;
  141.     }
  142.     return temp;
  143. }
  144.  
  145. void printTree(TreeNode* root, int space = 0)
  146. {
  147.     if (root == NULL)
  148.         return;
  149.  
  150.     // Increase distance between levels
  151.     int COUNT = 5;
  152.     space += COUNT;
  153.  
  154.     // Print right child first
  155.     printTree(root->right, space);
  156.  
  157.     // Print current node after space count
  158.     printf("\n");
  159.     for (int i = COUNT; i < space; i++)
  160.         printf(" ");
  161.     printf("%d\n", root->data);
  162.  
  163.     // Print left child
  164.     printTree(root->left, space);
  165. }
  166.  
  167. TreeNode* delete_BST(TreeNode* root, int key)
  168. {
  169.     if (root == NULL)
  170.     {
  171.         return root;
  172.     }
  173.  
  174.     if (key < root->data)
  175.     {
  176.         root->left = delete_BST(root->left, key);
  177.     }
  178.     else if (key > root->data)
  179.     {
  180.         root->right = delete_BST(root->right, key);
  181.     }
  182.     else
  183.     {
  184.         if (root->left == NULL)
  185.         {
  186.             TreeNode* temp = root->right;
  187.             free(root);
  188.             return temp;
  189.         }
  190.         else if (root->right == NULL)
  191.         {
  192.             TreeNode* temp = root->left;
  193.             free(root);
  194.             return temp;
  195.         }
  196.  
  197.         TreeNode* temp = find_minimum_iterative(root->right);
  198.         root->data = temp->data;
  199.         root->right = delete_BST(root->right, temp->data);
  200.     }
  201.     return root;
  202. }
  203.  
  204.  
  205.  
  206. int main()
  207. {
  208.  
  209.     TreeNode* root = NULL;
  210.  
  211.     root = insertion(root, 15);
  212.     root = insertion(root, 20);
  213.     root = insertion(root, 10);
  214.     root = insertion(root, 25);
  215.     root = insertion(root, 18);
  216.     root = insertion(root, 13);
  217.     root = insertion(root, 5);
  218.  
  219.     /// inorder(root);
  220.  
  221.     printTree(root);
  222.  
  223.     printf("Maximum Value: %d\n", find_maximum(root));
  224.     printf("Minimum Value: %d\n", find_minimum(root));
  225.  
  226.     printf("Root Immediate Previous: %d\n", find_maximum(root->left));
  227.     printf("Root Immediate Next: %d\n", find_minimum(root->right));
  228.  
  229.  
  230.     ///Deleting 5
  231.     root = delete_BST(root, 5);
  232.     printTree(root);
  233.  
  234.     return 0;
  235. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
          25

     20

          18

15

          13

     10

          5
Maximum Value: 25
Minimum Value: 5
Root Immediate Previous: 13
Root Immediate Next: 18

          25

     20

          18

15

          13

     10
https://ideone.com/MVvdh4
language:
C++ (gcc 8.3)
created:
16 days ago
visibility:
public

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!