#C_CODE: Binary tree - Morris traversal

#include <stdio.h>

#include <malloc.h>

typedef struct bintree tree;
struct bintree
{
    int data;
    tree *left;
    tree *right;
};

tree *newnode(int num)
{
    tree *r;
    r = (tree *)malloc(sizeof(tree));
    r->data = num;
    r->left = NULL;
    r->right= NULL;
    return (r);
}


void insert(tree **q, int num)
{
    tree *temp = *q;
    if(NULL == temp)
        *q = newnode(num);
    else
    {
        if(num <= temp->data) insert(&(temp->left),num);
        else insert(&(temp->right),num);
    }
}

/* Compute the no. of nodes in the tree */
int size(tree *temp)
{
    if (NULL == temp) return 0;
    else return (size(temp->left) + 1 + size(temp->right));
}

void display(tree *temp)
{
    tree *cur, *pre;
    if(NULL == temp) return;
    cur = temp;

    while(NULL != cur)
    {
        if(NULL == cur->left)
        {
            printf("%d ",cur->data);
            cur = cur->right; 
        }
        else
        {
            pre = cur->left;
            while(pre->right != NULL && pre->right != cur)
                pre = pre->right;
            if(pre->right == NULL)
            {
                pre->right = cur;
                cur = cur->left;
            }
            else
            {
                pre->right = NULL;
                printf("%d ",cur->data);
                cur = cur->right;
            }
        }
    }
}

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

void preorder(tree *temp)
{
    if(temp != NULL)
    {
        printf("%d ",temp->data);
        preorder(temp->left);
        preorder(temp->right);
    }
}

void postorder(tree *temp)
{
    if(temp != NULL)
    {
        postorder(temp->left);
        postorder(temp->right);
        printf("%d ",temp->data);
    }
}
int numarr[10] = {7,4,1,3,0,5,2,8,6,9};
int main()
{
    tree *root = NULL;
    int i;

    for(i=0; i<10; i++)
        insert(&root,numarr[i]);

    printf("\nThe no. of nodes in the tree: %d\n",size(root));    

    printf("\ninorder: ");
    inorder(root);
    
    printf("\npreorder: ");
    preorder(root);

    printf("\npostorder: ");
    postorder(root);

    printf("\nMorris traversal: ");
    display(root); 
    return 0;
}