inOrder(), preorder(), postOrder(), intsert(), delete() , find(), BST ADT with operations
Write C++ code to implement BST ADT with operations inOrder(), preorder(), postOrder(), intsert(), delete() & find() and understand its basic operations.

Objectives of this program:
1) Understand the data structure BST and its basic operations.
2) Understand the method of constructing the BST ADT and defining its operations.

Algorithm:
template<class T>
class BST;
template<class T>
class treenode*
{
friend class BST<T>;
private: treenode *left;
T data;
treenode* right;
};
template<class T>
class BST
{
private:
treenode<T> *root;
Public:
int isEmpty();
void inOrder(treenode<T> *node);
void preOrder(treenode<T> *node);
void postOrder(treenode<T> *node);
int insert(T item);
int delete(T item);
treenode<T>* find(treenode<T> *tree, T item);
}
template<class T>
int BST<T>::isEmpty()
{
if (root==NULL)
return 1;
else
return 0;
}
template<class T>
void BST<T>::inOrder(treenode<T> *currentnode)
{
if(currentnode!=NULL)

{
inOrder(currentnode->left);
cout<<currentnode->data;
inOrder(currentnode->right);
}
}
template<class T>
void BST<T>::preOrder(treenode<T> *currentnode)
{
if(currentnode!=NULL)
{
cout<<currentnode->data;
preOrder(currentnode->left);
preOrder(currentnode->right);
}
}
template<class T>
void BST<T>::postOrder(treenode<T> *currentnode)
{
if(currentnode!=NULL)
{
postOrder(currentnode->left);
postOrder(currentnode->right);
cout<<currentnode->data;
}
}
template<class T>
treenode<T> *BST<T>::find(treenode<T> *tree, T item)
{
if (!tree)
return NULL;
if (tree->data==item)
return tree;
else if(item<tree->data)
return find(t->left,x);
else
return find(t->right,x);
}
template<class T>
int BST<T>::insert(T item)//inserts item into BST. Returns 1 if successful
{
treenode<T>*p=root,*q=NULL;
while(p)
{
q=p;
if (p->data==item)
return 0; //item already in BST
if(item<p->data)
p=p->left;
else
p=p->right;
}
// makes the new BST node
p=new treenode<T>
p->left=p->right=NULL;
p->data=item;
if (!root) // if it is the first BST node
root=p;
else if (item<q->data)
q->left=p;
else
q->right=p;
return 1; //node successfully inserted
}
//deletes node with data equal to item from BST. returns 1 if deleted, else 0
template<class T>
int BST<T>::delete(T item)
{
treenode<T>*p=root,*q=NULL,*r=NULL;
while (p)
{
if(item<p->data)
p=p->left;
else if (item>p->data)
p=p->right;
else break;
}
return 0;
q=p->left;
while(q->right)
{
r=q;
T d=q->data;
q=q->right;
}
p->data=q->data;
r->right=q->left;
delete q;

return 1; //BST node deleted successfully
}

Thanks
Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..