 New update is available. Click here to update.

# 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).

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

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

// False if the right pointer points to its in-order successor
};

// 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
{
ptr = ptr -> right;
else
break;
}
}

// Create a new node
Node *value = new Node;
value -> data = key;

if (parent == NULL)
{
root = value;
value -> left = NULL;
value -> right = NULL;
}
else if (key < (parent -> data))
{
value -> left = parent -> left;
value -> right = parent;
parent -> left = value;
}
else
{
value -> left = parent;
value -> right = parent -> right;
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)

### 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.

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. 