#include <stdio.h>
#include <stdlib.h>

typedef struct tbtnode {
    char data;
    int rbit, lbit;
    struct tbtnode *rightc;
    struct tbtnode *leftc;
} tbtnode;

tbtnode* inordersucc(tbtnode *temp);

void create(tbtnode *head) {
    int flag;
    tbtnode *root, *temp, *curr;
    char ch = 'y', ch1;

    root = (tbtnode*)malloc(sizeof(tbtnode));
    printf("Enter data for root = ");
    scanf(" %c", &root->data);

    head->lbit = 1;
    root->leftc = head;
    root->rightc = head;
    root->lbit = 0;
    root->rbit = 0;
    head->leftc = root;

    do {
        flag = 0;
        temp = root;
        curr = (tbtnode*)malloc(sizeof(tbtnode));

        printf("Enter data = ");
        scanf(" %c", &curr->data);

        curr->lbit = 0;
        curr->rbit = 0;

        while (flag == 0) {
            printf("Do you want to insert this to left or right (l/r)? ");
            scanf(" %c", &ch1);

            if (ch1 == 'l') {
                if (temp->lbit == 0) {
                    curr->rightc = temp;
                    curr->leftc = temp->leftc;
                    temp->leftc = curr;
                    temp->lbit = 1;
                    flag = 1;
                } else {
                    temp = temp->leftc;
                }
            } else if (ch1 == 'r') {
                if (temp->rbit == 0) {
                    curr->leftc = temp;
                    curr->rightc = temp->rightc;
                    temp->rightc = curr;
                    temp->rbit = 1;
                    flag = 1;
                } else {
                    temp = temp->rightc;
                }
            }
        }

        printf("Do you wish to continue inserting data? (y/n) ");
        scanf(" %c", &ch);
    } while (ch == 'y');
}

void inorder(tbtnode *head) {
    tbtnode *temp = head;
    while (1) {
        temp = inordersucc(temp);
        if (temp == head)
            break;
        printf("%c ", temp->data);
    }
    printf("\n");
}

tbtnode* inordersucc(tbtnode *temp) {
    tbtnode *x = temp->rightc;
    if (temp->rbit == 1) {
        while (x->lbit == 1)
            x = x->leftc;
    }
    return x;
}

void preorder(tbtnode *head) {
    tbtnode *temp = head->leftc;
    while (temp != head) {
        printf("%c ", temp->data);
        while (temp->lbit != 0) {
            temp = temp->leftc;
            printf("%c ", temp->data);
        }
        while (temp->rbit == 0 && temp->rightc != head) {
            temp = temp->rightc;
        }
        temp = temp->rightc;
    }
}

int main() {
    tbtnode *head;
    head = (tbtnode*)malloc(sizeof(tbtnode));

    head->rbit = 1;
    head->lbit = 0;
    head->leftc = head;
    head->rightc = head;

    create(head);

    printf("Inorder traversal: ");
    inorder(head);

    printf("Preorder traversal: ");
    preorder(head);

    return 0;
}