Deletion in Binary Search Tree

Implementation

#include <iostream>
using namespace std;


struct _nod {
  int ky;
  struct _nod *Lft, *Rt;
};


// Creating a node in the binary tree.
struct _nod *nw_nod(int Itm) {
  struct _nod *temp = (struct _nod *)malloc(sizeof(struct _nod));
  temp->ky = Itm;
  temp->Lft = temp->Rt = NILL;
  return temp;
}


// now, we will see the traversal of the tree in the in-order form.
void in order(struct _nod *root) {
  if (root != NILL) {
    // traversing the tree from the left.
    inorder(root->Lft);


    // traversing the tree from the root.
    cout << root->ky << " -> ";


    // traversing the tree from the right.
    inorder(root->Rt);
  }
}


// inserting a new node in the tree.
struct _nod *insert(struct _nod *_nod, int ky) {
  // if the tree is empty, we must return the new node.
  if (_nod == NILL) return nw_nod(ky);


  // Now, we have to traverse to the right of the tree and insert a new node.
  if (ky < _nod->ky)
    _nod->Lft = insert(_nod->Lft, ky);
  else
    _nod->Rt = insert(_nod->Rt, ky);


  return _nod;
}


// creating a function to find out the in-order successor.
struct _nod *minValue_nod(struct _nod *_nod) {
  struct _nod *curr = _nod;


  // finding the left-most leaf node present in the tree.
  while (curr && curr->Lft != NILL)
    curr = curr->Lft;


  return curr;
}


// creating a function that will delete the node in the tree.
struct _nod *delete_nod(struct _nod *root, int ky) {
  // we have to return if the tree turns out to be empty.
  if (root == NILL) return root;


  // searching the node which is supposed to be deleted.
  if (ky < root->ky)
    root->Lft = delete_nod(root->Lft, ky);
  else if (ky > root->ky)
    root->Rt = delete_nod(root->Rt, ky);
  else {
    // the node is with the single child or no child at all, then:-
    if (root->Lft == NILL) {
      struct _nod *temp = root->Rt;
      free(root);
      return temp;
    } else if (root->Rt == NILL) {
      struct _nod *temp = root->Lft;
      free(root);
      return temp;
    }
    struct _nod *temp = minValue_nod(root->Rt);


    // placing the in-order successor where it is supposed to be deleted.
    root->ky = temp->ky;


    // creating a function that will delete the in-order successor.
    root->Rt = delete_nod(root->Rt, temp->ky);
  }
  return root;
}


// writing the main code.
int main() {
  struct _nod *root = NILL;
  root = insert(root, 8);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 6);
  root = insert(root, 7);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 4);


  cout << "Inorder traversal: ";
  inorder(root);


  cout << "\nAfter deleting 10\n";
  root = delete_nod(root, 10);
  cout << "Inorder traversal: ";
  inorder(root);
}

Output:

Example 2)

#include <stdio.h>
#include <stdlib.h>


struct _nod {
  int ky;
  struct _nod *Lft, *Rt;
};


// Creating a node in the binary tree.
struct _nod *nw_nod(int Itm) {
  struct _nod *temp = (struct _nod *)malloc(sizeof(struct _nod));
  temp->ky = Itm;
  temp->Lft = temp->Rt = NILL;
  return temp;
}


// now, we will see the traversal of the tree in the in-order form.
void in order(struct _nod *root) {
  if (root != NILL) {
    // traversing the tree from the left.
    inorder(root->Lft);
    // traversing the tree from the root.
    printf("%d -> ", root->ky);
    // traversing the tree from the right.
    inorder(root->Rt);
  }
}
// inserting a new node in the tree.
struct _nod *insert(struct _nod *_nod, int ky) {
  if (_nod == NILL) return nw_nod(ky);
  // Now, we have to traverse to the right of the tree and insert a new node.
  if (ky < _nod->ky)
    _nod->Lft = insert(_nod->Lft, ky);
  else
    _nod->Rt = insert(_nod->Rt, ky);


  return _nod;
}


// creating a function to find out the in-order successor.
struct _nod *minValue_nod(struct _nod *_nod) {
  struct _nod *curr = _nod;
  // finding the left-most leaf node present in the tree.
  while (curr && curr->Lft != NILL)
    curr = curr->Lft;


  return curr;
}
// creating a function that will delete the node in the tree.
struct _nod *delete_nod(struct _nod *root, int ky) {
  // Return if the tree is empty
  if (root == NILL) return root;
  // searching the node which is supposed to be deleted.
  if (ky < root->ky)
    root->Lft = delete_nod(root->Lft, ky);
  else if (ky > root->ky)
    root->Rt = delete_nod(root->Rt, ky);


  else {
    // the node is with the single child or no child at all, then:-
    if (root->Lft == NILL) {
      struct _nod *temp = root->Rt;
      free(root);
      return temp;
    } else if (root->Rt == NILL) {
      struct _nod *temp = root->Lft;
      free(root);
      return temp;
    }


    struct _nod *temp = minValue_nod(root->Rt);
    // placing the in-order successor where it is supposed to be deleted.
    root->ky = temp->ky;
    // creating a function that will delete the in-order successor.
    root->Rt = delete_nod(root->Rt, temp->ky);
  }
  return root;
}


// writing the main code.
int main() {
  struct _nod *root = NILL;
  root = insert(root, 8);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 6);
  root = insert(root, 7);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 4);


  printf("Inorder traversal: ");
  inorder(root);


  printf("\nAfter deleting 10\n");
  root = delete_nod(root, 10);
  printf("Inorder traversal: ");
  inorder(root);
}

Output: