Insertion in Threaded Binary Search Tree

Introduction

A. J. Perlis and C. Thornton have proposed a new binary tree called “Threaded Binary Tree“, which uses NULL pointers to improve its traversal process. In a threaded binary tree, NULL pointers are replaced by references of other nodes in the tree. These extra references are called threads. 

Although threads can be added to any binary tree, it is most efficient to add threads to a binary search tree or its variants, i.e. a tree that meets the Binary Search Tree properties. As a result, the Threaded Binary Tree we will create in this blog is a Binary Search Tree having Threads (threaded binary search tree).

Before moving on, we recommend you first read about the basics of Threaded Binary Tree.

Insertion in Threaded Binary Search Tree

The insertion technique is similar to that of a binary search tree. The only difference is that the threaded binary tree has to take into account the threads updates.

Node Structure of Threaded Binary tree

struct Node{
    int data;
    Node *left, *right;
    bool rightThread;
    bool leftThread;
 }

Let ‘value’ be the newly inserted node. Now, let’s look at the ways to insert a node:

Case 1: When a new node is inserted in an empty tree

The new node value becomes the root node, and both the left and right pointers of the value will be set to NULL. 

root = Value;

Value -> left = NULL;
Value -> right = NULL;

Case 2: When a new node is inserted as a left child

After inserting the node at its proper place, we will make its left and right child pointers point to in-order predecessor and successor, respectively. So the left and right threads of the new node will be:

value -> left = parent ->left;
value -> right = parent;

Before insertion, the left pointer of the parent was a thread, but after insertion, it will be a link pointing to the new node. 

parent -> leftThread = false;
parent -> left = value;

Case 3: When a new node is inserted as a right child

The node that was the parent’s in-order successor is now the in-order successor of this new node value. So the left and right threads of the new node will be:

value -> left = parent;
value -> right = parent -> right;

Before insertion, the right pointer of the parent was a thread, but after insertion, it will be a link pointing to the new node. 

parent -> rightThread = false;
parent -> right = value;

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;
}

Output

1  4  7  11  20  23  24  30  34

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)

Frequently Asked Questions

Key Takeaways

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. 

By: Mehak Goel