Week7

#include <iostream>
using namespace std;

struct node {
  int key;
  struct node *left, *right;
};

// Inorder traversal
void traverseInOrder(struct node *root) {
     if (root != NULL) {
        traverseInOrder(root->left);
        cout << root->key <<" ";
        traverseInOrder(root->right);
    }
}
//inserting
struct node *insertNode(struct node *node, int key) {
    
    if (node == NULL){
        struct node *newNode = new struct node;
        newNode->key = key;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    if (key < node->key)
        node->left = insertNode(node->left, key);
    else
        node->right = insertNode(node->right, key);
    return node;
    
}
/*returning the node with minimum key value found in that tree*/
struct node* minValueNode(struct node* node)
{
    struct node* current = node;
 
    /* loop down to find the leftmost leaf */
    while (current && current->left != NULL)
        current = current->left;
 
    return current;
}

// Deleting a node
struct node *deleteNode(struct node *root, int key) {
      
    // base case
    if (root == NULL)
        return root;
 
    // If the key to be deleted is smaller than the root's key,then it lies in the left subtree
    if (key < root->key)
        root->left = deleteNode(root->left, key);
 
    // If the key to be deleted is greater than key,then it is in the right subtree
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
 
    // if key is same as root's key, then it is the node to be deleted
    else {
        // if  node has no child
        if (root->left == NULL and root->right == NULL)
            return NULL;
 
        // node with only one child or no child
        else if (root->left == NULL) {
            struct node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            struct node* temp = root->left;
            free(root);
            return temp;
        }
 
        // node with two children: Get the inorder successor
        
        struct node* temp = minValueNode(root->right);
 
        // Copy the inorder successor's content to this node
        root->key = temp->key;
 
        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

// Driver code
int main() {
  struct node *root = NULL;

  int operation;
  int operand;
  cin >> operation;

  while (operation != -1) {
    switch(operation) {
      case 1: // insert
        cin >> operand;
        root = insertNode(root, operand);
        cin >> operation;
        break;
      case 2: // delete
        cin >> operand;
        root = deleteNode(root, operand);
        cin >> operation;
        break;
      default:
        cout << "Invalid Operator!\n";
        return 0;
    }
  }
  
  traverseInOrder(root);
}