Insertion in Threaded Binary Search Tree

Code for Insertion

We search the tree for the key, just like in a typical BST insertion. If the key is already present, we return from there. Otherwise, a new key is inserted at the end of the search. 

In BST, the search ends either when the key is found or when a NULL left or right pointer is reached. Except for the left and right NULL pointers of the first and last nodes, threads are used to replace all left and right NULL pointers. As a result, when we reach a NULL pointer or a thread, our search will fail.

#include<bits/stdc++.h>
using namespace std;
 
struct Node
{
    int data;
    Node *left, *right;
 
    // False if the left pointer points to its in-order predecessor
    bool leftThread;
 
    // False if the right pointer points to its in-order successor
    bool rightThread;
};
 
// Insertion of a Node in a Threaded Binary Tree
struct Node *insert(struct Node *root, int key)
{
    // Searching for a Node with given value
    Node *ptr = root;
    Node *parent = NULL; // Parent of key to be inserted
    while (ptr != NULL)
    {
        // If the key already exists, return it
        if (key == (ptr->data))
        {
            printf("Duplicate Key !\n");
            return root;
        }
 
        parent = ptr; // Update parent pointer
 
        // Moving on to the left subtree.
        if (key < ptr->data)
        {
            if (ptr -> leftThread == false)
                ptr = ptr -> left;
            else
                break;
        }
 
        // Moving on to the right subtree.
        else
        {
            if (ptr->rightThread == false)
                ptr = ptr -> right;
            else
                break;
        }
    }
 
    // Create a new node
    Node *value = new Node;
    value -> data = key;
    value -> leftThread = true;
    value -> rightThread = true;
 
    if (parent == NULL)
    {
        root = value;
        value -> left = NULL;
        value -> right = NULL;
    }
    else if (key < (parent -> data))
    {
        value -> left = parent -> left;
        value -> right = parent;
        parent -> leftThread = false;
        parent -> left = value;
    }
    else
    {
        value -> left = parent;
        value -> right = parent -> right;
        parent -> rightThread = false;
        parent -> right = value;
    }
 
    return root;
}
 
// Returns the inorder successor using rightThread
struct Node *inorderSuccessor(struct Node *ptr)
{
    // If rightThread is set, we can quickly find
    if (ptr -> rightThread == true)
        return ptr->right;
 
    // Else return leftmost child of right subtree
    ptr = ptr -> right;
    while (ptr -> leftThread == false)
        ptr = ptr -> left;
    return ptr;
}
 
// Printing of the threaded tree
void inorder(struct Node *root)
{
    if (root == NULL)
        printf("Tree is empty");
 
    // In leftmost node
    struct Node *ptr = root;
    while (ptr -> leftThread == false)
        ptr = ptr -> left;
 
    // One by one print successors
    while (ptr != NULL)
    {
        cout<<ptr -> data<<"  ";
        ptr = inorderSuccessor(ptr);
    }
}
 
// Driver Program
int main()
{
    struct Node *root = NULL;
 
    root = insert(root, 23);
    root = insert(root, 4);
    root = insert(root, 30);
    root = insert(root, 11);
    root = insert(root, 7);
    root = insert(root, 34);
    root = insert(root, 20);
    root = insert(root, 24);
    root = insert(root, 1);


    inorder(root);


    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

1  4  7  11  20  23  24  30  34

You can also try this code with Online C++ Compiler

Run Code

Time complexity – O(h), where h is the height of the threaded binary search tree. The height of the tree can be ‘n’ in the worst case and all the keys are inserted in ascending or descending order(Skewed Tree) where all the nodes except the leaf have only one child and we may have to travel from to root to the deepest leaf node

Space complexity – O(1)

You can also read about insertion into bst and Data Structure.

Frequently Asked Questions

What is the advantage of a threaded binary tree over a binary tree?

In a Threaded Binary Tree, every node that does not have a left or right child is linked to its in-order predecessor or successor using a thread. By doing this threading, we avoid the recursive method of traversing a binary tree that uses stacks and consumes a lot of space and time.

What are the disadvantages of a Threaded Binary Tree?

Some disadvantages of a Threaded Binary Tree are:

1. Since we store the inorder predecessor/successor for the node with a null left/right pointer, Insertion and deletion of nodes are more time-consuming and complex in the threaded binary tree.

2. We use additional memory in the form of leftThread and rightThread boolean variables to distinguish between a thread from an ordinary link.

Conclusion

In this article, we learned how a node is inserted in a threaded binary search tree. Three cases were depicted here, the first case occurs when the tree was empty, and the newly inserted node becomes the parent node. The second and third cases occur when the new node is inserted as the left or right child pointers. 

Recommended Problems:

• Burn Tree
• Size of largest BST in a Binary Tree.
• Aggressive Cows
• Partial BST