Th

 #include <stdio.h>

#include <stdlib.h>

typedef struct ThreadedNode {

    int data;

    struct ThreadedNode *left, *right;

    int rightThread; // 1 if right pointer is a thread, otherwise 0

} ThreadedNode;

// Function prototypes

ThreadedNode* createNode(int data);

ThreadedNode* insert(ThreadedNode* root, int data);

ThreadedNode* leftMost(ThreadedNode* node);

void inorderTraversal(ThreadedNode* root);

void menu();

int main() {

    ThreadedNode* root = NULL;

    int choice, data;

    while (1) {

        menu();

        printf("Enter your choice: ");

        scanf("%d", &choice);

        switch (choice) {

            case 1:

                printf("Enter the data to insert: ");

                scanf("%d", &data);

                root = insert(root, data);

                break;

            case 2:

                printf("Inorder traversal: ");

                inorderTraversal(root);

                printf("\n");

                break;

            case 3:

                exit(0);

            default:

                printf("Invalid choice! Please try again.\n");

        }

    }

    return 0;

}

// Function to create a new node

ThreadedNode* createNode(int data) {

    ThreadedNode* newNode = (ThreadedNode*)malloc(sizeof(ThreadedNode));

    if (!newNode) {

        printf("Memory error\n");

        return NULL;

    }

    newNode->data = data;

    newNode->left = newNode->right = NULL;

    newNode->rightThread = 0;

    return newNode;

}

// Function to insert a node in the threaded binary tree

ThreadedNode* insert(ThreadedNode* root, int data) {

    ThreadedNode* newNode = createNode(data);

    if (!root) {

        return newNode;

    }

    ThreadedNode* current = root;

    ThreadedNode* parent = NULL;

    while (current != NULL) {

        parent = current;

        if (data < current->data) {

            if (current->left == NULL) {

                break;

            }

            current = current->left;

        } else {

            if (current->rightThread) {

                break;

            }

            current = current->right;

        }

    }

    if (data < parent->data) {

        parent->left = newNode;

        newNode->right = parent;

        newNode->rightThread = 1;

    } else {

        newNode->right = parent->right;

        newNode->rightThread = parent->rightThread;

        parent->right = newNode;

        parent->rightThread = 0;

    }

    return root;

}

// Function to find the left-most node in a tree/subtree

ThreadedNode* leftMost(ThreadedNode* node) {

    while (node != NULL && node->left != NULL) {

        node = node->left;

    }

    return node;

}

// Function for inorder traversal

void inorderTraversal(ThreadedNode* root) {

    if (root == NULL) {

        return;

    }

    ThreadedNode* current = leftMost(root);

    while (current != NULL) {

        printf("%d ", current->data);

        if (current->rightThread) {

            current = current->right;

        } else {

            current = leftMost(current->right);

        }

    }

}

// Function to display the menu

void menu() {

    printf("\nMenu:\n");

    printf("1. Insert Node\n");

    printf("2. Inorder Traversal\n");

    printf("3. Exit\n");

}