Binary Search Tree

bst.cpp

#include <iostream>

using namespace std;

struct Node
{
  int value;
  Node* left;
  Node* right;
};

struct Head
{
  Node* next;
};

class BST
{
  public:
    BST();
    ~BST();

    void ins_node(int value);
    Node* del_node(Node* head, int value);
    void del_all_nodes(Node* head);
    bool search(int value);
    void print(Node* head);

    Head* head;
};

BST::BST()
{
  head = new Head();
  head->next = NULL;
}

BST::~BST()
{
  del_all_nodes(head->next);
  if (head != NULL) {
    delete head;
    head = NULL;
  }
}

void BST::ins_node(int value)
{
  Node* new_node = new Node();
  new_node->value = value;
  new_node->left = NULL;
  new_node->right = NULL;

  Node* tree = head->next;
  if (tree == NULL) {
    head->next = new_node;
  }

  while (tree != NULL) {
    if (value < tree->value) {
      if (tree->left != NULL) {
        tree = tree->left;
      } else {
        tree->left = new_node;
        break;
      }
    } else if (value > tree->value) {
      if (tree->right != NULL) {
        tree = tree->right;
      } else {
        tree->right = new_node;
        break;
      }
    } 
  }
}

Node* BST::del_node(Node* head, int value)
{
  Node* tree = head;
  while(tree != NULL) {
    if (tree->value == value) {
      break;
    } else if (tree->value > value) {
      tree = tree->left;
    } else {
      tree = tree->right;
    }
  }

  if (tree == NULL) {
    cout << "Node not exists!" << endl;
    return NULL;
  }

  // If node has left and right sub-tree both
  if (tree->left && tree->right) {
    // get the smallest value of right sub-tree
    Node* smallest = tree->right;
    while (smallest->left != NULL) {
      smallest = smallest->left;
    }
    tree->value = smallest->value;
    tree->right = del_node(tree->right, smallest->value);
  }
  else {
    Node* temp = tree;

    if (tree->left) {
      tree = tree->left; 
    } else {
      tree = tree->right;
    }

    delete temp;
    temp = NULL;
  }
  return tree;
}

void BST::del_all_nodes(Node* head)
{
  if (head == NULL) {
    return ;
  }

  del_all_nodes(head->left);
  del_all_nodes(head->right);
  delete head;
  head = NULL;
}

bool BST::search(int value)
{
  bool is_exists = false;
  Node* tree = head->next;

  while (tree != NULL) {
    if (tree->value == value) {
      is_exists = true;
      break;
    } else if (tree->value > value) {
      tree = tree->left;
    } else {
      tree = tree->right;
    }
  }

  return is_exists;
}

void BST::print(Node* head)
{
  if (head == NULL) {
    return ;
  }

  cout << head-> value << ' ';
  print(head->left);
  print(head->right);
}

int main(int argc, char* argv[])
{
  BST bst;
  int numbers[] = {5, 3, 2, 4, 6, 8};

  for (int i=0; i<6; i++) {
    bst.ins_node(numbers[i]);
  }
  bst.print(bst.head->next);
  cout << endl;

  for (int i=0; i<6; i++) {
    if (bst.search(numbers[i])) {
      cout << numbers[i] << " exists!" << endl;
    }
  }

  for (int i=0; i<6; i++) {
    cout << "Deletion" << endl;
    bst.del_node(bst.head->next, numbers[i]);
    bst.print(bst.head->next);
    cout << endl;
  }

  return 0;
}