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