Untitled

/*
week 8
1> write a program to delete a node from a binary search tree.

    leaf level
    subtree level 
    root deletion
reconstruct the tree after deletion

Implement a heap using top down aproach to construct a min heap.

*/
#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int key;
    struct node *left, *right;
};
 

struct node* newNode(int item)
{
    struct node* temp
        = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(struct node* root)
{
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}
 

struct node* insert(struct node* node, int key)
{

    if (node == NULL)
        return newNode(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);

    return node;
}
 

struct node* minValueNode(struct node* node)
{
    struct node* current = node;
 
  
    while (current && current->left != NULL)
        current = current->left;
 
    return current;
}
 

struct node* deleteNode(struct node* root, int key)
{

    if (root == NULL)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
 

    else if (key > root->key)
        root->right = deleteNode(root->right, key);

    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;
        }
 

        struct node* temp = minValueNode(root->right);
 

        root->key = temp->key;
 

        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

int main()
{

    struct node* root = NULL;
    int c=1;
    do{
    printf("\nOperations:\n1. Insert node into tree\n2. Inorder traversal\n3. Delete a node\n4. Exit\nEnter your choice: ");
      int ch;
    scanf("%d",&ch);
  
    int x;
    switch(ch){
    case 1: 
    printf("\nEnter value to insert: ");
    scanf("%d",&x);
    root=insert(root,x);
    break;
    case 2:
    printf("\nInorder traversal of the tree:\n");
    inorder(root);
    break;
    case 3: 
    printf("\nEnter value to delete: ");
    scanf("%d",&x);
    root=deleteNode(root,x);
    break;
    case 4:
    c=0;
    break;
    }
    
    }while(c==1);

 
    return 0;
}