fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct node {
  5.   int key;
  6.   struct node *left, *right;
  7. };
  8.  
  9. struct node *newNode(int item) {
  10.   struct node *temp = (struct node *)malloc(sizeof(struct node));
  11.   temp->key = item;
  12.   temp->left = temp->right = NULL;
  13.   return temp;
  14. }
  15.  
  16. void inorder(struct node *root) {
  17.   if (root != NULL) {
  18.  
  19.     inorder(root->left);
  20.  
  21.     cout << root->key << " -> ";
  22.  
  23.     inorder(root->right);
  24.   }
  25. }
  26.  
  27. // Insert a node
  28. struct node *insert(struct node *node, int key) {
  29.   // Return a new node if the tree is empty
  30.   if (node == NULL) return newNode(key);
  31.  
  32.   // Traverse to the right place and insert the node
  33.   if (key < node->key)
  34.     node->left = insert(node->left, key);
  35.   else
  36.     node->right = insert(node->right, key);
  37.  
  38.   return node;
  39. }
  40.  
  41. // Find the inorder successor
  42. struct node *minValueNode(struct node *node) {
  43.   struct node *current = node;
  44.  
  45.   // Find the leftmost leaf
  46.   while (current && current->left != NULL)
  47.     current = current->left;
  48.  
  49.   return current;
  50. }
  51.  
  52. // Deleting a node
  53. struct node *deleteNode(struct node *root, int key) {
  54.   // Return if the tree is empty
  55.   if (root == NULL) return root;
  56.  
  57.   // Find the node to be deleted
  58.   if (key < root->key)
  59.     root->left = deleteNode(root->left, key);
  60.   else if (key > root->key)
  61.     root->right = deleteNode(root->right, key);
  62.   else {
  63.     // If the node is with only one child or no child
  64.     if (root->left == NULL) {
  65.       struct node *temp = root->right;
  66.       free(root);
  67.       return temp;
  68.     } else if (root->right == NULL) {
  69.       struct node *temp = root->left;
  70.       free(root);
  71.       return temp;
  72.     }
  73.  
  74.     // If the node has two children
  75.     struct node *temp = minValueNode(root->right);
  76.  
  77.     // Place the inorder successor in position of the node to be deleted
  78.     root->key = temp->key;
  79.  
  80.     // Delete the inorder successor
  81.     root->right = deleteNode(root->right, temp->key);
  82.   }
  83.   return root;
  84. }
  85.  
  86. // Driver code
  87. int main() {
  88.   struct node *root = NULL;
  89.   root = insert(root, 100);
  90.   root = insert(root, 20);
  91.   root = insert(root, 122);
  92.   root = insert(root, 6072);
  93.   root = insert(root, 9);
  94.   root = insert(root, 1);
  95.   root = insert(root, 2);
  96.   root = insert(root, 87);
  97.  
  98.   cout << "Inorder traversal: ";
  99.   inorder(root);
  100.  
  101.   cout << "\nAfter deleting 10\n";
  102.   root = deleteNode(root, 100);
  103.   cout << "Inorder traversal: ";
  104.   inorder(root);
  105. }
Success #stdin #stdout 0s 5424KB
comments (?)
stdin
copy 
45
stdout
copy 
Inorder traversal: 1 -> 2 -> 9 -> 20 -> 87 -> 100 -> 122 -> 6072 -> 
After deleting 10
Inorder traversal: 1 -> 2 -> 9 -> 20 -> 87 -> 122 -> 6072 ->
https://ideone.com/LqWfk7
language:
C++14 (gcc 8.3)
created:
1 year 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!