#include <stdio.h>
#include <stdlib.h>
 
struct Node {
   int data;
   struct Node* left;
   struct Node* right;
   int isThreaded; // 1 if right pointer points to in-order successor, 0 otherwise
};
 
// Function prototype
struct Node* leftMost(struct Node* node);

// Create a new node
struct Node* newNode(int data) {
   struct Node* node = (struct Node*)malloc(sizeof(struct Node));
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   node->isThreaded = 0;
   return node;
}
 
// Function to perform an in-order traversal of threaded binary tree
void inOrder(struct Node* root) {
   struct Node* curr = leftMost(root);
 
   while (curr != NULL) {
       printf("%d ", curr->data);
 
       if (curr->isThreaded) {
           curr = curr->right;
       } else {
           curr = leftMost(curr->right);
       }
   }
}
 
// Helper function to find the leftmost node in a binary tree
struct Node* leftMost(struct Node* node) {
   if (node == NULL)
       return NULL;
   while (node->left != NULL)
       node = node->left;
   return node;
}
 
// Function to insert a node into the threaded binary tree
struct Node* insert(struct Node* root, int data) {
   if (root == NULL)
       return newNode(data);
 
   // Find the position to insert the new node
   if (data < root->data) {
       root->left = insert(root->left, data);
   } else {
       // If the right child is not present, we attach the new node and thread it
       root->right = insert(root->right, data);
       if (root->right->left == NULL) {
           root->right->left = root;
           root->right->isThreaded = 1;
       }
   }
 
   return root;
}
 
int main() {
   struct Node* root = NULL;
   root = insert(root, 20);
   root = insert(root, 10);
   root = insert(root, 30);
   root = insert(root, 5);
   root = insert(root, 15);
 
   printf("In-order traversal of threaded binary tree: \n");
   inOrder(root);
   printf("\n");
 
   return 0;
}