BINARY SEARCH TREE

A binary search tree (BST) is a tree in which all nodes follows the below mentioned properties −

• The left sub-tree of a node has key less than or equal to its parent node's key.
• The right sub-tree of a node has key greater than or equal to its parent node's key.

Thus, a binary search tree (BST) divides all its sub-trees into two segments; left sub-tree and right sub-tree and can be defined as −

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

Representation

BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has key and associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

An example of BST −

We observe that the root node key (27) has all less-valued keys on the left sub-tree and higher valued keys on the right sub-tree.

Basic Operations

Following are basic primary operations of a tree which are following.

• Search − search an element in a tree.
• Insert − insert an element in a tree.
• Delete – delete an element in a tree.
• Preorder Traversal − traverse a tree in a preorder manner.
• Inorder Traversal − traverse a tree in an inorder manner.
• Postorder Traversal − traverse a tree in a postorder manner.

Node

Define a node having some data, references to its left and right child nodes.

struct node {

   int data;  

   struct node *leftChild;

   struct node *rightChild;

};

Search Operation

Whenever an element is to be search. Start search from root node then if data is less than key value, search element in left subtree otherwise search element in right subtree.

Insert Operation

Whenever an element is to be inserted. First locate its proper location. Start search from root node then if data is less than key value, search empty location in left subtree and insert the data. Otherwise search empty location in right subtree and insert the data.

Delete Operation

In this, we can delete a element .

·        First we search the our required element.

·        Removal is also going to be search process.

·        The BST is un-balanced tree during deletion and insertion

#include<conio.h>
#include<stdlib.h>
#include<iostream.h>
struct node
{
  int info;
  struct node *left;
  struct node *right;
};
typedef struct node tree ;
tree *root=NULL;
class BIN
{
  int num;
  tree *p,*prev,*temp;
  public:
  void insert();
  void inorder(tree *);
  void postorder(tree *);
  void preorder(tree *);
  void display();
};
void BIN:: insert()
{
  p=new(tree);
  cout<<"\n Enter  number:";
  cin>>num;
  p->info=num;
  p->left=p->right=NULL;
  if(root==NULL)
  {
    root=p;
    return;
  }
  temp=root;
  while(temp!=NULL)
  {
    if(num>=temp->info)
    {
      prev=temp;
      temp=temp->right;
    }
    else
    {
      prev=temp;
      temp=temp->left;
    }
  }
  if(num>=prev->info)
    prev->right=p;
  else
    prev->left=p;
}
void BIN::preorder(tree *temp)
{
  if(temp!=NULL)
  {
    cout<<" "<<temp->info;
    preorder(temp->left);
    preorder(temp->right);
  }
}
void BIN:: inorder(tree *temp)
{
  if(temp!=NULL)
  {
    inorder(temp->left);
    cout<<" "<<temp->info;
    inorder(temp->right);
  }
}
void  BIN::postorder(tree *temp)
{
  if(temp!=NULL)
  {
    postorder(temp->left);
    postorder(temp->right);
    cout<<" "<<temp->info;
  }
}
void BIN:: display()
{
  if(root==NULL)
  {
    cout<<"\n ***EMPTY TREE**** \n";
    return;
  }
  cout<<"\n\n THE PREORDER DISPLAY IS:   ";
  preorder(root);
  cout<<"\n\n THE INORDER DISPLAY IS:   ";
  inorder(root);
  cout<<"\n\n THE POSTORDER DISPLAY IS:   ";
  postorder(root);
}
void main()
{
  BIN o;
  int ch=1;
  int count=0;
  clrscr();
  while(ch)
  {
    cout<<"\n***********MENU***********";
    cout<<"\n1:INSERT-IN-TREE\n2:DISPLAY\n3.QUIT\n";
    cout<<"\nEnter your choice:\n";
    cin>>ch;
    switch(ch)
    {
      case 1:clrscr();
         count++;
         o.insert();
         break;
      case 2:clrscr();
      cout<<"\n\n THE NUMBER OF NODES IN THE BST is "<< count;
      o.display();
      break;
      case 3:exit(0);
    }
  }
  getch();
}