A Simple Insertion Approach in Single Threaded Binary Tree by@hsnice

if you have done (or doing) **Data Structures** , then you definitely got to (or will get to ) familiar with Binary Tree, and shall know (or hear) something about Threaded Binary Tree .

I was studying Binary Tree Data Structure , then I got to know about Threaded Binary Tree . After going through its theory part, I was curious about its implementation (Basically how insertion takes place in it ?) .

So, first I googled to see if any easy( to grasp) implementation for insertion operation exists or not. But on googling , I don’t found any implementation which was easy to grasp.

Then I decided to do it by my own, and After some time, I found an implementation of insertion operation which I think can be easily grasped by anyone.

After that, I decided why not I write an article on it. So that it can reach to large audience.

So here is the article !

Before we move on insertion implementation in Threaded Binary Tree . I think it will be good if we discuss a little about Single Threaded Binary Tree.

The idea ofSingle Threaded Binary Treeis to maketraversal faster and do it without using any stack or recursion in Binary Trees. In Single Threaded Binary Tree , a NULL right pointer(of a node) is made to point to`in-order`

successor (it it exists).`in-order`

I am always mentioning its full name (Single Threaded Binary Tree) because a Double Threaded Binary Tree also exist (in this both NULL left and right pointer is made to point to in-order predecessor and in-order successor).

**Node Contains : **each node (circles in picture) contains

```
// c++
// Node structure
struct Node
{
int key; // value in node
Node *left, *right; // stores left/right child
bool rightThread; // stores right Thread for node exists or not
};
```

**First** , for inserting a new node we will follow the same rule of insertion used in BST . For a node, if new value to insert is smaller than value present in node then new node(with new value) will go in left subtree of node and if new value to insert is larger value than in node , it will go in right subtree of node.

**Second ,** and for making thread ( on which this article mainly focuses ) we will follow following steps :

1. As we can see from just above picture, that we should have the knowledge of node (in-order successor) with which we are gonna make a thread .

For this , I decided to maintain a variable which stores the node with which we have to make thread.

`Node *successor = NULL;`

‘ **NULL** ’ denotes that variable ‘ **successor** ’ does not contain any value right now.

2. We can also see (from picture), that we need to make a thread, only if a new node is gonna inserted as left child( or left descendent) of any node .

So , At the time of finding position for new node . we will store value in ‘ **successor** ’ whenever new node will be inserted as left child for a node(already present in tree) .

```
// c++
// left subtree
if (curr->key > el) // curr is a variable maintaining current node(already present in tree)
// with which comparison is taking place
// And, el is new key we have to insert
{
successor = curr; // successor only contain value if new node
// goes in left subtree of curr node
curr = curr->left; // go left subtree
}
```

3. If new node is going to store as right child ( during finding position for new node) of a node already present in tree , then we will first check if ‘

**right Thread**

‘ value for current node is As now , there is no

`right Thread`

exist , it has its right child.```
// c++
// right subtree
if (curr->key < el)
{
if (curr->rightThread) // if current node has rightThread == true
{
curr->right = NULL; // make right child null of current node
curr->rightThread = false; // change value of rightThread for current node from true to false
}
curr = curr->right; // go right subtree
}
```

4. Finally when we come out of position finding loop (for new node), if successor value does not remains ‘ **NULL** ‘ (with which we initialize it) . we will store successor value as right child of new node and makes

**right Thread**

```
// c++
// adding thread
if (successor) // if successor is not NULL
{
// newNode stores data of new node
newNode->right = successor; // store successor value in right child of newNode
newNode->rightThread = true; // makes rightThread valur of new Node to true
}
```

This is my idea for insertion in Single Threaded Binary Tree , which I found easy.

Thank you for reading it till the end 🙂 !

And If you are curious to see full implementation of Threaded Binary Tree , you may look at this.

**References you may find useful :**

Join Hacker Noon

Create your free account to unlock your custom reading experience.