Answer to Question #204234 in Algorithms for Haider

Question

Implementation the following function using Binary Search trees

I. Create BST.

II. Deletion of BST.

III. Searching maximum and minimum value in BST.

Answer 1

//creation of the BST node
struct node* newNode(int item)
{
    struct node* temp
        = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
// Deletion of the BST
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 and root.right==NULL):
            return NULL
       
  
        elif (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;
}

// Searching of the nodes
int findMax(Node* root)
{
   if (root == NULL)
   return INT_MIN;
   int res = root->data;
   int lres = findMax(root->left);
   int rres = findMax(root->right);
   if (lres > res)
        res = lres;
   if (rres > res)
        res = rres;
   return res;
}
// searching of the minimum node
int findMin(struct Node* root)
{
  if (root == NULL)
  return INT_MAX;
    int res = root->data;
    int lres = findMin(root->left);
    int rres = findMin(root->right);
    if (lres < res)
      res = lres;
    if (rres < res)
      res = rres;
    return res;
}