Skip to main content

Create an in-order threaded binary search tree and perform the traversals.(Single thread)

CODE:


 #include <iostream>


using namespace std;


// Node structure for the threaded binary search tree

struct Node {

    int data;

    Node* left;

    Node* right;

    bool rightThread; // Indicates if the right pointer is a thread

};


// Function to create a new node

Node* createNode(int data) {

    Node* newNode = new Node();

    newNode->data = data;

    newNode->left = newNode->right = nullptr;

    newNode->rightThread = false;

    return newNode;

}


// Function to insert a node into the threaded binary search tree

void insert(Node*& root, int data) {

    Node* newNode = createNode(data);

    Node* curr = root;

    Node* prev = nullptr;


    while (curr != nullptr) {

        prev = curr;

        if (data < curr->data) {

            if (curr->left != nullptr)

                curr = curr->left;

            else

                break;

        } else {

            if (curr->right != nullptr && !curr->rightThread)

                curr = curr->right;

            else

                break;

        }

    }


    if (prev == nullptr) {

        root = newNode;

    } else if (data < prev->data) {

        newNode->right = prev;

        prev->left = newNode;

    } else {

        newNode->right = prev->right;

        prev->right = newNode;

        prev->rightThread = false;

    }

}


// Function to perform in-order traversal of the threaded binary search tree

void inOrderTraversal(Node* root) {

    Node* curr = root;


    while (curr != nullptr) {

        while (curr->left != nullptr)

            curr = curr->left;


        cout << curr->data << " ";


        if (curr->rightThread)

            curr = curr->right;

        else {

            curr = curr->right;

            if (curr != nullptr)

                cout << curr->data << " ";

        }

    }

}


int main() {

    Node* root = nullptr;


    // Inserting elements into the threaded binary search tree

    insert(root, 5);

    insert(root, 3);

    insert(root, 7);

    insert(root, 2);

    insert(root, 4);

    insert(root, 6);

    insert(root, 8);


    // Performing in-order traversal

    cout << "In-order traversal: ";

    inOrderTraversal(root);

    cout << endl;


    return 0;

}







Popular posts from this blog

Write a program to create a class Student2 along with two method getData (), printData () to get the value through argument and display the data in printData. Create the two objects s1, s2 to declare and access the values from class STtest.

 CODE: import java.util.Scanner; class Student2 {     private String name;     private int age;          // Method to set data     public void getData(String name, int age) {         this.name = name;         this.age = age;     }          // Method to print data     public void printData() {         System.out.println("Name: " + name);         System.out.println("Age: " + age);     } } public class STtest {     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);                  // Creating objects of Student2 class         Student2 s1 = new Student2();         Student2 s2 = new Student2();              ...
Read more

Create an in-order threaded binary search tree and perform the traversals.(Double Thread)

 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) {                ...
Read more

Create a BST and find inorder successor and inorder predecessor of specific node.

CODE: #include <iostream> using namespace std; // Node definition struct Node {     int data;     Node* left;     Node* right;     Node(int val) {         data = val;         left = nullptr;         right = nullptr;     } }; // Insertion in BST Node* insert(Node* root, int val) {     if (root == nullptr) {         return new Node(val);     }     if (val < root->data) {         root->left = insert(root->left, val);     } else {         root->right = insert(root->right, val);     }     return root; } // Finding inorder successor Node* findInorderSuccessor(Node* root, Node* target) {     if (target->right != nullptr) {         Node* current = target->right;         while (current->l...
Read more