CODE:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
bool leftThread;
bool rightThread;
};
Node* createThreadedBST(int arr[], int n) {
Node* root = nullptr;
for (int i = 0; i < n; ++i) {
Node* newNode = new Node;
newNode->data = arr[i];
newNode->left = newNode->right = nullptr;
newNode->leftThread = newNode->rightThread = true;
if (root == nullptr) {
root = newNode;
} else {
Node* current = root;
Node* parent = nullptr;
while (true) {
parent = current;
if (newNode->data < current->data) {
if (!current->leftThread) {
current = current->left;
} else {
newNode->left = current->left;
newNode->right = current;
current->leftThread = false;
current->left = newNode;
break;
}
} else {
if (!current->rightThread) {
current = current->right;
} else {
newNode->left = current;
newNode->right = current->right;
current->rightThread = false;
current->right = newNode;
break;
}
}
}
}
}
return root;
}
void inOrderTraversal(Node* root) {
Node* current = root;
while (current != nullptr) {
while (!current->leftThread) {
current = current->left;
}
cout << current->data << " ";
while (current->rightThread && current->right != nullptr) {
current = current->right;
cout << current->data << " ";
}
current = current->right;
}
}
int main() {
int arr[] = {6, 3, 8, 1, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
Node* root = createThreadedBST(arr, n);
cout << "In-order traversal of the threaded BST: ";
inOrderTraversal(root);
cout << endl;
return 0;
}
