bstree.cpp

Binary Search Tree Implementation with extra features like Maximum Depth of a tree, Minimum element

#include<iostream>
using namespace std;
class tree
{
public:
    int value;
    class tree *left,*right;
    void append(tree**,int),disp_inorder(tree *),disp_postorder(tree *),
    disp_preorder(tree *),min_ele(tree *),mirror(tree *),add(tree **,int);
    int max_depth(tree *);
};
void tree::append(tree** head,int n)
{
    tree *temp=(tree *)malloc(sizeof(tree *)),*thead=*head;
    int flag=0;
    if(temp==NULL)
    {
        cout<<"\nHeap Full!!!"<<endl;
        exit(1);
    }
    else
    {
        temp->value=n;
        temp->left=temp->right=NULL;
    }
    if(*head==NULL)//add at beginning
    {
    temp->right=temp->left=NULL;
    *head=temp;flag=1;
    }
    else//add at right or left--non-recursive
    {
        while(!flag){
        while(thead->value >= n && !flag)
        {
            if(thead->value==n)goto cantadd;
        if(thead->left!=NULL)thead=thead->left;//points to left node
            else
            {
            thead->left=temp;
            flag=1;
            }
        }
        while(thead->value <= n && !flag)
        {
            if(thead->value==n)goto cantadd;
        if(thead->right!=NULL)thead=thead->right;//points to left node
            else
            {
            thead->right=temp;
            flag=1;
            }
        }
      }//ends main while loop
    }
cout<<"\nItem added to tree!!"<<endl;
    cantadd:
        {
            if(!flag)
            {
                cout<<"\nCant add...No duplicates allowed!!"<<endl;
                free(temp);
            }
        }
}
void tree::disp_inorder(tree *h)
{
    if(h==NULL)
        return ;
    else
    {
      disp_inorder(h->left);
      cout<<h->value<<"  ";
      disp_inorder(h->right);
    }
}
void tree::disp_postorder(tree *h)
{
    if(h==NULL)
        return ;
    else
    {
      disp_postorder(h->left);
      disp_postorder(h->right);
      cout<<h->value<<"  ";
    }
}
void tree::disp_preorder(tree *h)
{
    if(h==NULL)
        return ;
    else
    {
      cout<<h->value<<"  ";
      disp_preorder(h->left);
      disp_preorder(h->right);
    }
}
int tree::max_depth(tree *h)
{
    if(h==NULL)
        return 0;
    else{
        int ldep=max_depth(h->left);
        int rdep=max_depth(h->right);
        if(ldep < rdep)
            return(rdep+1);
        else
            return(ldep+1);
    }
}
void tree::min_ele(tree *h)//non-recursive
{
    if(h!=NULL){
    for(;h->left!=NULL;h=h->left);
    cout<<"\nMinimum element is :"<<h->value<<endl;
    }
    else
        cout<<"\nTree Empty!!"<<endl;
}
void tree::mirror(tree *h)
{
    if(h==NULL)
        return;
    else
    {
        tree *temp;
        mirror(h->left);//for sub-trees
        mirror(h->right);
        temp=h->left;//swap left and right
        h->left=h->right;
        h->right=temp;
    }
}
void tree::add(tree **head,int num)
{
    if(*head==NULL)
    {
        (*head)=(tree *)malloc(sizeof(tree *));
        (*head)->left=(*head)->right=NULL;(*head)->value=num;
    }
    else
    {
        if((*head)->value > num)
            add(&((*head)->left),num);
        else if((*head)->value < num)
            add(&((*head)->right),num);
        else if((*head)->value == num)
            cout<<"\nCant add...No duplicates allowed!!"<<endl;
    }
cout<<"\nItem added to tree!!"<<endl;
}
int main()
{
    int n,ch;
    tree *h=NULL,obj;
    do
    {
        cout<<"\n\n\t\tMENU\n1.append\n2.display_inorder\n3.display_postorder\n4."<<
        "display_preorder\n5.max_depth of tree\n6.min_element\n7.Mirror\n8.exit\n\n"<<
        "Enter your choice :"<<endl;
        cin>>ch;
        switch(ch)
        {
            case 1:
                cout<<"\nEnter the number to be appended :"<<endl;
                cin>>n;
                cout<<"\n\n1.Use-Recursive\n2.Non-Recursive\n\nEnter your choice :"
                <<endl;
                cin>>ch;
                if(ch==1)
                    obj.add(&h,n);
                else
                    obj.append(&h,n);
                break;
            case 2:
                cout<<"\nInorder traversal is :";
                obj.disp_inorder(h);
                break;
            case 3:
                cout<<"\nPostorder traversal is :";
                obj.disp_postorder(h);
                break;
            case 4:
                cout<<"\nPreorder traversal is :";
                obj.disp_preorder(h);
                break;
            case 5:
                cout<<"\nMax_Depth of the tree :"<<obj.max_depth(h)<<endl;
                break;
            case 6:
                obj.min_ele(h);
                break;
            case 7:
                if(h==NULL)
                    cout<<"\nTree empty!!"<<endl;
                else{
                    obj.mirror(h);
                    cout<<"\nTree Mirrored!!"<<endl;
                }
                break;
            case 8:
                exit(0);
            default:
                cout<<"\nEnter a value b/n 1 & 7"<<endl;
        }
    }while(ch!=8);
return 0;
}