Untitled

#include <iostream>

using namespace std;

struct node {

    int data;

    struct node *left;

    struct node *right;
    
    bool rightthread;

    bool leftthread;

};


struct node *insert(struct node *root, int key){
    
    struct node *ptr = root;

    struct node *par = NULL; 

    while (ptr != NULL){
        
        if (key == (ptr->data)){

            cout<<endl<<"Duplicate Key !\n";

            return root;
        }
 
        par = ptr;
 
        if (key < ptr->data){

            if (ptr -> leftthread == false){

                ptr = ptr -> left;

            }
            else{

                break;

            }
        }
 
        else{

            if (ptr->rightthread == false){

                ptr = ptr -> right;

            }
            else{

                break;

            }
        }
    }

    struct node *t = new node;

    t-> data = key;

    t-> leftthread = true;

    t-> rightthread = true;
 
    if (par == NULL){

        root = t;

        t -> left = NULL;

        t -> right = NULL;

    }

    else if (key < (par -> data)){

        t -> left = par -> left;

        t -> right = par;

        par -> leftthread = false;

        par -> left = t;

    }

    else{

        t -> left = par;

        t -> right = par -> right;

        par -> rightthread = false;

        par -> right = t;

    }
 
    return root;
}

/*struct node *leftmost(struct node *n){

    if(n==NULL){

        return NULL;

    }

    while(n->left!=NULL){

        n=n->left;

    }

    return n;

};


void inorder(struct node *root){

    struct node *curr = leftmost(root);

    while(curr!=NULL){

        cout<<curr->data<<" ";

        if (curr->rightthread){

            curr = curr->right;

        }

        else{

            curr = leftmost(curr->right);

        }

    }

}*/

struct node *inorderSuccessor(struct node *ptr){
    
    if (ptr -> rightthread == true){

        return ptr->right;

    }
 
    ptr = ptr -> right;

    while (ptr -> leftthread == false){

        ptr = ptr -> left;
    
    }

    return ptr;
}
 

void inorder(struct node *root){

    if (root == NULL){

        cout<<endl<<"Tree is empty"<<endl;

    }
 
    struct node *ptr = root;

    while (ptr -> leftthread == false){

        ptr = ptr -> left;

    }
 
    while (ptr != NULL){

        cout<<ptr->data<<" ";

        ptr = inorderSuccessor(ptr);

        //cout<<endl;

    }
}


struct node *preorderSuccessor(struct node *ptr){

    if(ptr->leftthread==false){

        return ptr->left;

    }

     while (ptr->rightthread==true){

        ptr =ptr->right;
    
    }

    return ptr->right;

}

void preorder(struct node *root){

    if (root == NULL){

        cout<<endl<<"Tree is empty"<<endl;

    }

    struct node *ptr = root;

    ptr=ptr->left;

    while(ptr!=NULL){

        cout<<ptr->data<<" ";

        ptr=preorderSuccessor(ptr);

    }

}

int main(){

    int a,c,n;

    struct node *root = NULL;

    cout<<"\nEnter the Value of root node \n";

    cin>>n;


    root=insert(root,n);

    do
    {
        cout<<"\n1]Insert a node \n2]Inorder \n3]Preorder \n4]Exit \n"<<endl<<"Enter the choice :";

        cin>>c;

        cout<<endl;

        switch (c)
        {
        case 1:

            cout<<endl<<"Enter the no. to Insert"<<endl;

            cin>>a;

            root=insert(root,a);

            break;
        
        case 2:

            inorder(root);

            cout<<endl;

            break;

        case 3:

            preorder(root);

            cout<<endl;

            break;

        }

    }while (c!=4);

}