Tree-Morris_Inorder

// <-------------------[sWitCHcAsE]---------------------->

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct NODE {

        int data;
        NODE *left;
        NODE *right;
};

NODE * insert(NODE *root, int data) {
    if(root==NULL) {
        root=(NODE*)malloc(sizeof(NODE));
        root->left=root->right=NULL;
        root->data=data;
        return root;
    }
    else {
        while(root!=NULL) {
            if(root->data>data) {
                if(root->left!=NULL) root=root->left;
                else break;
            }
            else {
                if(root->right!=NULL) root=root->right;
                else break;
            }
        }
        NODE *new_node=new NODE;
        new_node->data=data;
        new_node->left=new_node->right=NULL;
        if(root->data > data) {
            root->left=new_node;
        }
        else root->right=new_node;
        return new_node;
    }
}

void inorder(NODE *root) {
    if(root!=NULL) {
        inorder(root->left);
        printf("%d ",root->data);
        inorder(root->right);
    }
}

void MorrisInorder(NODE *root) {
    NODE* current,*pre;
    current=root;
    while(current!=NULL) {
        if(current->left==NULL) {
            printf("%d ",current->data);
            current=current->right;
        }
        else {
            pre=current->left;
            while(pre->right != NULL && pre->right !=current)
                pre=pre->right;
            if(pre->right==NULL) {
                pre->right=current;
                current=current->left;
            }
            else {
                pre->right=NULL;
                printf("%d ",current->data);
                current=current->right;
            }
        }
    }
}

int main() {
    NODE *root=NULL;
    root=insert(root,100);
    insert(root,110);
    insert(root,200);
    insert(root,90);
    insert(root,80);
    insert(root,12);
    insert(root,19);
    insert(root,1);
    insert(root,1000);
    inorder(root);
    cout<<endl;
    cout<<"MORRIS INORDER"<<endl;
    MorrisInorder(root);
}