Answer to Question #284568 in C++ for Ahmed Ali

Question

1) Create a Binary Search Tree (BST) that perform the following operations:

- Insertion of a node in BST

- Deletion of a node in BST

- Searching a node in BST

Answer 1

#include<iostream>
using namespace std;

class BST {
   
  struct node {
    int data;
    node* left;
    node* right;
  };

  node* root;

  node* insert(int x, node* t)
  {
    if(t == NULL)
    {
      t = new node;
      t->data = x;
      t->left = t->right = NULL;
    }
    else if(x < t->data)
      t->left = insert(x, t->left);
    else if(x > t->data)
      t->right = insert(x, t->right);
    return t;
  }

  node* remove(int x, node* t) {
    node* temp;
    if(t == NULL)
      return NULL;
    else if(x < t->data)
      t->left = remove(x, t->left);
    else if(x > t->data)
      t->right = remove(x, t->right);
    else if(t->left && t->right)
    {
      temp = findMin(t->right);
      t->data = temp->data;
      t->right = remove(t->data, t->right);
    }
    else
    {
      temp = t;
      if(t->left == NULL)
        t = t->right;
      else if(t->right == NULL)
        t = t->left;
      delete temp;
    }

    return t;
  }

  node* find(node* t, int x) {
    if(t == NULL)
      return NULL;
    else if(x < t->data)
      return find(t->left, x);
    else if(x > t->data)
      return find(t->right, x);
    else
      return t;
  }

public:
  BST() {
    root = NULL;
  }

  ~BST() {
    root = makeEmpty(root);
  }

  void insert(int x) {
    root = insert(x, root);
  }

  void remove(int x) {
    root = remove(x, root);
  }

  void search(int x) {
    root = find(root, x);
  }
};