C++ Program to Implement the operation in BINARY SEARCH TREE (BST)

C++ Program for  BINARY SEARCH TREE

DESCRIPTION:

A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree.

Binary Search tree is-
1. A data structure for efficient searching, insertion and deletion
    
Binary search tree property
For every node X
* All the keys in its left subtree are smaller than the key value in X
* All the keys in its right subtree are larger than the key value in X

Below Image Shows a Tree in which one Left side tree is BST and Right side tree is not a BST.

OUTPUT OF THE PROGRAM

SOURCE CODE:

#include<iostream>

#include<conio .h>

#include <stdlib.h>
using namespace std;
struct node
{
int info;
node *left,*right;
};
node *root=NULL,*loc,*par;
void find(int item, node *root);
void insertion();
void traversal(node *root);


int main()
{
int k;
while(1)
{
cout<<endl<<" ---1---Insertion"; cout<<endl<<" ---2---Traversal"; cout<<endl<<" ---3---Exit"; cout<<endl<<endl ; cout<<endl<<"Enetr Your Choice: "; cin>>k; switch(k)
{
case 1:

insertion();
break;
case 2:
traversal(root);
break;
case 3:
exit(0);
}
}
}
void find(int item, node *root)
{
     node *ptr,*save;
          if(root==NULL)
          {
               loc=NULL;
               par=NULL;
               return;
           }
         else if(item==root->info)
           {
               loc=root;
               par=NULL;
               return;
           }
         else
         {
              if(iteminfo)
                {
                   ptr=root->left;
                   save=root;
                }
             else
               {
                   ptr=root->right;
                   save=root;
               }
             while(ptr!=NULL)
               {
                    if(item==ptr->info)
                      {
                          loc=ptr;
                          par=save;
                          return;
                      }
                    else
                    {
                     if(iteminfo)
                      {
                          save=ptr;
                          ptr=ptr->left;
                      }
                    else
                      {
                           save=ptr;
                           ptr=ptr->right;
                      }
                    }
                    }
                    }
               loc=NULL;
               par=save;
        }

void insertion()
{
node *avail,*new1;
int item;
cout<<"ENTER THE ITEM : ";
cin>>item;
find(item,root);
if(loc!=NULL)
{
      cout<<endl<< "ITEM ALREADY PRESENT"; return;
}
else
{
avail=new node;
new1=avail;
new1->info=item;
loc=new1;
new1->left=NULL;
new1->right=NULL;
if(par==NULL)
root=new1;
else if(iteminfo)
par->left=new1;
else
par->right=new1;
}
}

void traversal(node *root)
{
if(root==NULL)
{
    return;
}
else
{
traversal(root->left);
cout<<"   "<info;
traversal(root->right);
}
}


/* IF U FOUND ANY PROBLEM IN THIS PROGRAM  OR IF YOU HAVE ANY QUERY RELATED THIS PROGRAM THEN PLEASE COMMENT ON THIS POST  OR YOU CAN DIRECTLY MAIL ME ON piyushkhandelwal029@gmail.com . */

THANKU. 

SHARE

Admin

• 
• 
• 
• 
•