Skip to main content

Create a threaded binary search tree with insert, search and delete leaf node operations.

 CODE:


#include <iostream>

using namespace std;


// Node structure for the threaded binary search tree

struct Node {

    int key;

    Node* left;

    Node* right;

    bool isThreaded; // Indicates if right pointer is a thread

};


// Function to create a new node

Node* createNode(int key) {

    Node* newNode = new Node;

    newNode->key = key;

    newNode->left = nullptr;

    newNode->right = nullptr;

    newNode->isThreaded = false;

    return newNode;

}


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

Node* insert(Node* root, int key) {

    // If tree is empty, create a new node

    if (root == nullptr) {

        return createNode(key);

    }

    

    // Traverse the tree to find the appropriate position

    Node* curr = root;

    Node* prev = nullptr;

    while (curr != nullptr) {

        prev = curr;

        if (key < curr->key) {

            if (curr->left == nullptr) {

                curr->left = createNode(key);

                curr->left->right = curr;

                curr->left->isThreaded = true;

                return root;

            }

            curr = curr->left;

        } else {

            if (curr->isThreaded) {

                Node* temp = curr->right;

                curr->right = createNode(key);

                curr->isThreaded = false;

                curr->right->right = temp;

                curr->right->isThreaded = true;

                return root;

            }

            curr = curr->right;

        }

    }

    

    // If key is already present, return root

    return root;

}


// Function to search for a key in the threaded binary search tree

bool search(Node* root, int key) {

    Node* curr = root;

    while (curr != nullptr) {

        if (key == curr->key) {

            return true;

        } else if (key < curr->key) {

            curr = curr->left;

        } else {

            if (curr->isThreaded) {

                break;

            }

            curr = curr->right;

        }

    }

    return false;

}


// Function to delete a leaf node from the threaded binary search tree

Node* deleteLeaf(Node* root, int key) {

    // If tree is empty, return root

    if (root == nullptr) {

        return root;

    }

    

    // Search for the node to delete

    Node* curr = root;

    Node* prev = nullptr;

    while (curr != nullptr && curr->key != key) {

        prev = curr;

        if (key < curr->key) {

            curr = curr->left;

        } else {

            if (curr->isThreaded) {

                break;

            }

            curr = curr->right;

        }

    }

    

    // If key not found, return root

    if (curr == nullptr) {

        return root;

    }

    

    // If the node to be deleted has children, return root

    if (curr->left != nullptr || !curr->isThreaded) {

        return root;

    }

    

    // If the node is root and has no children

    if (curr == root) {

        delete curr;

        return nullptr;

    }

    

    // Update pointers of parent node

    if (prev->left == curr) {

        prev->left = curr->left;

        prev->isThreaded = true;

    } else {

        prev->right = curr->right;

    }

    

    // Delete the node

    delete curr;

    

    return root;

}


int main() {

    Node* root = nullptr;

    

    // Insert some nodes

    root = insert(root, 50);

    root = insert(root, 30);

    root = insert(root, 20);

    root = insert(root, 40);

    root = insert(root, 70);

    root = insert(root, 60);

    root = insert(root, 80);

    

    // Search for a key

    cout << "Is 40 present in the tree? " << (search(root, 40) ? "Yes" : "No") << endl;

    cout << "Is 90 present in the tree? " << (search(root, 90) ? "Yes" : "No") << endl;

    

    // Delete a leaf node

    root = deleteLeaf(root, 40);

    cout << "Is 40 present in the tree after deletion? " << (search(root, 40) ? "Yes" : "No") << endl;

    

    return 0;

}







Popular posts from this blog

krushnaaa

  import java . awt .* ; import java . awt . event .* ; public class SimpleAWTExample {     public static void main ( String [] args ) {         // Create a Frame         Frame frame = new Frame ( "Simple AWT Example" );         // Create a Button         Button button = new Button ( "Click Me!" );         // Set layout for the Frame         frame . setLayout ( new FlowLayout ());         // Add the Button to the Frame         frame . add ( button );         // Set size of the Frame         frame . setSize ( 300 , 200 ); // Width: 300 pixels, Height: 200 pixels         // Make the Frame visible         frame . setVisible ( true );         // Add a WindowListener to handle closing event     ...
Read more

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